#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010, M = 100010;

char s[M], p[N];

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i ++)
        cin >> p[i];

    int m;
    cin >> m;
    for(int j = 0; j < m; j ++)
        cin >> s[j];

    int i = 0, j = 0;
    while(i < strlen(s) && j < strlen(p))
    {
        if(p[j] == s[i])
        {
            i ++;
            j ++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if(j == strlen(p))   cout << "匹配成功" << endl;
    else cout << "匹配失败" << endl;
    return 0;
}

kmp写法

#include <iostream>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];//p为子串, s为母串;

int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;//p,m下标都从1开始

    //next[N],ne[1] = 0;a与自己找最长前后缀就是0所以不用求 // 就是找子串最长的与前缀相等的后缀长
    for(int i = 2, j = 0; i <= n; i ++)// ababaa;
    {
        while(j && p[j + 1] != p[i])    
            j = ne[j];
        if(p[j + 1] == p[i])    j ++;   
        ne[i] = j;//
    }
    //kmp匹配
    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && p[j + 1] != s[i])
            j = ne[j];
        if(p[j + 1] == s[i])    j ++;//证明下一个位置匹配了
        if(j == n)
        {
            cout << i - n << " ";
            j = ne[j];
        }
    }
    return 0;
}