题目描述 （KMP + 字符串哈希）

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

输入格式
第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围
1≤N≤105
1≤M≤106

样例

输入样例：

3
aba
5
ababa

输出样例：

0 2

算法1

(KMP)

y总的模板代码

C++ 代码

#include<iostream>

using namespace std;
const int N = 1e5+10, M = 1e6+10;
int n,m;
char p[N],s[M];
int ne[N];
int main()
{
    cin>>n>>p+1>>m>>s+1;//KMP习惯上下标从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)
        {
            cout<<i-n<<' ';
            j = ne[j];
        }
    }
    return 0;
}

算法2

(字符串哈希) 运用的还很青涩，不会的同学可以参考一下

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5 + 10, M = 1e6 +10, X = 131;
typedef unsigned long long ULL;

int n,m;
int hp[M],hs[M], x[M];
char p[N], s[M];
ULL get1(int l, int r){
    return hp[r] - hp[l - 1] * x[r - l + 1];
}
ULL get2(int l, int r){
    return hs[r] - hs[l - 1] * x[r - l + 1];
}
int main()
{
   cin>>n>>p+1>>m>>s+1;
   x[0] = 1;
   for(int i = 1; i <= m; i ++){
       x[i] = x[i - 1] * X;
       if(p[i]) hp[i] = hp[i - 1] * X + p[i];
       hs[i] = hs[i - 1] * X + s[i];
   }
   for(int i = 1; i <= m; i ++){
       if(get1(0,n) == get2(i,i+n-1)) printf("%d ",i - 1);
   }
    return 0;
}