题目

样例

输入样例：

3
aba
5
abab

输出样例：

0 2

思路

思想

终极思想：匹配失败后，模板串（下面红线）最大向后移动多少位，可以节省暴力比较次数

那么最大向后移动多少位，只和模板串的性质有关捏

在每次失配时，不是把p串往后移一位，而是把p串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next[ ]数组确定的。

next数组的含义及手动模拟

对next[ j ] ，是p[ 1, j ]串中前缀和后缀相同的最大长度（部分匹配值），即 p[ 1, next[ j ] ] = p[ j - next[ j ] + 1, j ]

例如：

手动模拟求next数组：对 p = “abcab”

对next[ 1 ] ：前缀 = 空集—————后缀 = 空集—————next[ 1 ] = 0;

对next[ 2 ] ：前缀 = { a }—————后缀 = { b }—————next[ 2 ] = 0;

对next[ 3 ] ：前缀 = { a , ab }—————后缀 = { c , bc}—————next[ 3 ] = 0;

对next[ 4 ] ：前缀 = { a , ab , abc }—————后缀 = { a . ca , bca }—————next[

4 ] = 1;

对next[ 5 ] ：前缀 = { a , ab , abc , abca }————后缀 = { b , ab , cab ,

bcab}————next[ 5 ] = 2;

匹配思路

s串和p串都是从1开始的。i 从1开始，j 从0开始，每次s[ i ] 和p[ j + 1 ]比较

当匹配过程到上图所示时，

s[ a , b ] = p[ 1, j ] && s[ i ] != p[ j + 1 ] 此时要移动p串（不是移动1格，而是直接移动到下次能匹配的位置）

其中1串为[ 1, next[ j ] ]，3串为[ j - next[ j ] + 1 , j ]。由匹配可知 1串等于3串，3串等于2串。所以直接移动p串使1到3的位置即可。这个操作可由j = next[ j ]直接完成。 如此往复下去，当 j == m时匹配成功。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
char p[N],s[M];
int ne[N];
int n,m;
int main()
{
    cin>>n>>p+1>>m>>s+1;
    // 求next数组
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    // 匹配
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n)
        {
            printf("%d ",i-n);
            j=ne[j];
        }
    }
    return 0;
}