假设我们拥有一种能力 $O_1$ 能找到最大的的前缀使 $s[1…k] = s[n-k-1,n]$;

我们可以让模式串 $p$ 以及待匹配串 $s$ 做如下操作:

定义 $t = p + “\#” + s$;

我们得到了 $t$ 注意这里的 “#” 必须不包含在 $p$ 与 $s$ 中

那么我们逐一从 $t$ 的 “#” 位置后面开始遍历,用我们假设提到的能力想想会发生什么？

没错如果最大前缀长度就是 $p$ 的大小那么这个位置就是刚好是匹配上位置的尾端

也就是 $i - \text{int}(p.\text{size()} + 1)$

那么匹配到的位置就是 $i - \text{int}(p.\text{size()} + 1) - \text{int}(p.\text{size()})$

那么问题就解决了

回到第一个问题中

如何 $O_1$ 得到最大匹配串呢？

考虑 $dp[i]$ 表示为当前最大匹配串

那么如果当前 $s[i] == s[j]$; $dp[i] = dp[i-1] + 1$;

否则找到先前匹配 $j$ 的最大位置直到 $s[i]==s[j]$;

如果找不到那么就让当前的 $dp[i] = 0$ 即可

参考代码:

std::vector<int> kmp(const std::string &s) {
    int n = int(s.size());
    std::vector<int> dp(n + 1);
    for (int i = 1, j = 0; i < n; ++i) {
        while (j && s[i] != s[j]) j = dp[j];
        j += (s[i] == s[j]);
        dp[i + 1] = j;
    }
    return dp;
}
void solve() {
    int n, m;
    std::string p, s;
    std::cin >> n >> p >> m >> s;
    auto f = kmp(p + "#" + s);
    for (int i = int(p.size() + 1); i < int(f.size()); ++i) {
        if (f[i] == int(p.size())) std::cout << i - int(p.size() + 1) - int(p.size()) << ' ';
    }
}