字符串匹配

使用的写法是《数据结构》–严蔚敏书上改进的版本
（对于aaaaaaab这类字符串性能上稍有提升）

输入样例

4
aaab
14
aaaaabaabaaaab

输出样例

2 10

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;
int n, m;
char p[N], s[M];
int ne[N];

int main(){
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;

    int i = 1, j = 0;
    while(i <= n){
        if( j == 0 || p[i] == p[j]){
            ++i, ++j;
            ne[i] = p[i] == p[j] ? ne[j] : j;
        }
        else j = ne[j];
    }

    i = 1, j = 1;
    while(i <= m && j <= n){
        if(j == 0 || s[i] == p[j]){
            ++i, ++j;
        }
        else j = ne[j];
        if(j == n + 1){
            printf("%d ", i - j);
            j = ne[n + 1];
        }
    }
    return 0;
}

next[]数组中存储的值

0 0 0 3
上述方法中下标是从1开始的，
串”aaab”中，第2和3个字符失配时，我们直接将模式串指针置为0，那么我们下一次进行匹配时主串和模式串都会往前移动一个单位（如果不加优化，next数组中的值应当为0 1 2 3，而这里面包含了两次多余的操作）