[C++知识库]最后的轻语 KMP

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int ne[N];
char s[N], p[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s%s", s + 1, p + 1);
        int n = strlen(s + 1);
        int m = strlen(p + 1);
        for (int i = 2, j = 0; i <= n; i++)
        {
            while (j && s[i] != s[j + 1])
                j = ne[j];
            if (s[i] == s[j + 1])
                j++;
            ne[i] = j;
        }
        int f = 0;
        for (int i = 1, j = 0; i <= m; i++)
        {
            while (j && p[i] != s[j + 1])
                j = ne[j];
            if (p[i] == s[j + 1])
                j++;
            if (!j)
            {
                printf("NO\n");
                f = 1;
                break;
            }
        }
        if (!f)
            printf("YES\n");

        for (int i = 1; i <= n; i++)
            ne[i] = 0;
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖