编辑代码

#include <bits/stdc++.h>
using namespace std;

void query(string s1, string s2)
{
    int i = 0, j = 0;
    while (i <= s1.size() - s2.size())
    {
        if (s1[i] != s2[j])
            i++;
        else
        {
            int k = i;
            while (k < s1.size() && j < s2.size() && s1[k] == s2[j])
            {
                k++;
                j++;
            }
            if (j == s2.size())
            {
                cout << i++ << ' ';
                j = 0;
            }
            else
            {
                j = 0;
                i = i + 1;
            }
        }
    }
}

void get_next(int *next, string s2)
{
    next[0] = -1;
    int j = -1;
    int i = 0;
    while (i < s2.size())
    {
        if (j == -1 || s2[i] == s2[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

int kmp(string s1, string s2, int *next)
{
    
    int i = 0, j = 0;
    while ( i < (int)s1.size() && j < (int)s2.size() )
    {
        // cout<<s1.size()<<' '<<s2.size();
        if (j==-1 ||  s1[i] == s2[j])
                {i++;j++;}
        else
            j=next[j];
    }
    if (j==s2.size())
    return i-j;
    else
    return -1;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;

    int *next;
    next = (int *)malloc(sizeof(int) * s2.size());
    memset(next, 0, sizeof(int));

    get_next(next, s2);

    int pos=kmp(s1,s2,next);
    cout<<pos;
    return 0;
}