KMP

按从小到大的顺序输出s2在s1中出现的位置。

//KMP算法  （前缀）   kmp[0] = kmp[1] = 0
int nxt[N];
string s1, s2;
void KMP(int len, string s)
{
    int j = 0;
    s = " " + s;
    for (int i = 2; i <= len; i++)
    {
        while (j && s[j + 1] != s[i])
            j = nxt[j];
        if (s[j + 1] == s[i])
            j++;
        nxt[i] = j;
    }
}
inline void solve() {
    cin >> s1 >> s2;
    int l1 = s1.size(), l2 = s2.size();
    KMP(l2, s2);
    s1 = " " + s1, s2 = " " + s2;
    int j = 0;
    for (int i = 1; i <= l1; i++) {
        while (j&&s2[j + 1] != s1[i])
            j = nxt[j];
        if (s2[j + 1] == s1[i]) j++;
        if (j == l2) {
            cout << i - l2 + 1 << endl;//匹配成功，输出s2在s1中出现的位置
            j = nxt[j];
        }
    }
}