看到 OI Wiki 上有关 KMP 的一个不算惊为天人但也有点意思的做法，水一水。

众所周知 KMP 是为了解决字符串匹配问题的，有一个长度为 $n$ 的模式串 $t$ 和一个文本串 $s$。

我们构造一个字符串 $t+\#+s$​​​​，其中 $\#$​​​​ 是既不在 $t$​​​​ 中也不在 $s$​​​​ 中的一个字符。

求这个字符串的前缀数组（即 $nxt$ 函数），那么在该字符串中 $nxt[i]=n$​ 的位置就是一个匹配。

char a[maxn]; // 字符串从 1 开始
char b[maxn];
int n, m;
int nxt[maxn];

void solve()
{
    for (int i = 2, j = 0; i <= n + 1 + m; i++)
    {
        while (j && a[i] != a[j + 1])
            j = nxt[j];
        if (a[i] == a[j + 1])
            j++;
        nxt[i] = j;
    }
    for (int i = n + 2; i <= n + 1 + m; i++)
        if (nxt[i] == n)
            cout << i - 2 * n << endl;
}