题目描述

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

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

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

样例

输入样例：
3
aba
5
ababa
输出样例：
0 2

算法1

(字符串哈希)

时间复杂度

$O(n)$

C++ 代码

#include<iostream>
using namespace std;

typedef unsigned long long ULL;

const int M = 1000010;
const int q = 13331;

ULL Q[M], S[M];


ULL get(int l, int r)
{
    return S[r] - S[l - 1] * Q[r - l + 1];
}

int main()
{
    int n, m;
    string p, s;
    cin >> n >> p >> m >> s;
    s = " " + s;

    ULL  pp = 0;
    for(int i = 0; i < n; i ++) pp = pp * q + p[i];
    ULL t = 0;
    S[0] = 0;

    for(int i = 1; i <= m; i ++)
        S[i] = S[i - 1] * q + s[i];

    Q[0] = 1;
    for(int i = 1; i <= n; i ++) Q[i] = Q[i - 1] * q;

    for(int l = 1; l + n - 1 <= m ; l ++)
    {
        int r = l + n - 1;
        if(get(l ,r) == pp) cout << l - 1 << " ";
    }


    return 0;

}

算法2

(KMP) $O(n^2)$

blablabla

时间复杂度

$O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char s[M], p[N];
int ne[N];

int main()
{
    scanf("%d%s%d%s", &n, p + 1, &m, s + 1);        

    for(int i = 2, j = 0; i <= n; i ++)
    {
        ne[1] = 0;                                  
        while(j && p[i] != p[j + 1]) j = ne[j];     

        if(p[i] == p[j + 1]) j ++;                 
        if(j == 0) continue;                       

        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 == 0) continue;

        if(j == n)
        {
            printf("%d ", i - n);                 
            j = ne[j];                              
        }
    }

    return 0;
}