题目描述

给定一个字串s，再给定一个字串p，p在s中多次出现，输出每次作为子串时的起始下标；

样例

3
aba
5
ababa

算法1

KMP $O(m+n)$

kmp是对暴力做法的一种优化，尝试在一次遍历时尽量少往后回退，为做到这种效果，就需要一个next数组来存储回退的位置，从而在遍历不匹配的时候根据next数组回退；
+ next数组建立的过程就是字串p与自己匹配的过程；
+ next数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标；
+ 先处理next数组第一个元素的原因是如果第一个元素都不匹配那必然是重新开始比较字串；

时间复杂度

C++ 代码

#include<iostream>
using namespace std;

int main()
{
    int n, m;
    string p, s;
    cin>>n>>p>>m>>s;
    int ne[n];                                      //用来保存字串p的next数组；
    ne[0] = -1;                                     //如果第一个元素不匹配则回退到字符串没进行比较时
    //进行next数组的处理
    for(int i = 1, j = -1; i < n; ++i){
        while(j >= 0 && p[i] != p[j+1]) j = ne[j];  //若匹配不成功，且索引j不在字串里，则回退到能够匹配的前缀最长的子串最后下标；
        if(p[i] == p[j+1]) ++j;                     //如果当前元素与索引j的下一个元素相等，则可以将索引j指向它的下一个元素；
        ne[i] = j;                                  //除第一个元素已处理外，每个元素都应有一个对应回退的位置；
    }
    //根据next数组进行匹配
    for(int i = 0, j = -1; i < m; ++i){
        while(j >= 0 && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) ++j;
        if(j == n-1)
            printf("%d ", i-n+1);                   //若匹配成功则输出当前匹配字串的起始坐标
    }
    return 0;
}

算法2

字符串哈希 $O(m)$

做了下面的字符串哈希题，立马回来把kmp这个题重新用字符串哈希做一次；

C++ 代码

#include<iostream>
using namespace std;

typedef unsigned long long ULL;
const int N = 1e6+7, P = 131;
ULL h[N], p[N];

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

int main()
{
    int n, m;
    string sub, s;
    cin>>n>>sub>>m>>s;
    p[0] = 1;
    ULL subHash = 0;                //子字串不需要多次寻找，于是用一个ULL变量存储；
    for(int i = 0; i < m; ++i){
        p[i+1] = p[i] * P;
        h[i+1] = h[i] * P + s[i];
        if(i < n)
            subHash = subHash * P + sub[i];
    }
    for(int i = 0; i <= m-n; ++i)   //循环m-n+1次，找主字串中与子字串哈希值相同的位置；
        if(get(i, i+n-1) == subHash)
            cout<<i<<' ';
    return 0;
}