题目描述

给定一个模式串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

主要考点

KMP算法

注意事项

公共前后缀的条件：
1. 最长的公共前后缀
2. 不包含字符串本身

next[i] = j的含义为：
含义1. 模板串第 i 个字母与主串对应字母不匹配时,模板串下一个要与主串对应字母匹配的位置为 j + 1
含义2. next[i] = j, 表示 t[1, j] = t[i - j + 1, i], 即以 i 结尾的最长公共前后缀的长度为 j

C ++ 代码1

#include <iostream>
using namespace std;

const int M = 1000010, N = 100010;

char s[M], t[N];//分别表示主串和模板串
int ne[N];//ne[i] = j,表示模板串第i个字母与主串对应字母不匹配时,模板串下一个匹配的位置为j
int lens, lent;//分别表示主串长度和模板串长度

//next函数
void get_next(char s[], char t[]){
    for(int i = 2, j = 0; i <= lent; i ++){
        while(j && t[i] != t[j + 1]) j = ne[j];
        if(t[i] == t[j + 1]) j ++;
        ne[i] = j;
    }
}

//kmp算法, 匹配过程
void kmp(char s[], char t[]){
    for(int i = 1, j = 0; i <= lens; i ++){
        while(j && s[i] != t[j + 1]) j = ne[j];
        if(s[i] == t[j + 1]) j ++;
        if(j == lent){//匹配成功
            cout << i - lent << ' ';
            j = ne[j];
        }
    }
}

int main(){
    cin >> lent >> t + 1 >> lens >> s + 1;
    get_next(s, t);
    kmp(s, t);
    return 0;
}

注意事项

next[i] = j的含义为：
含义1. 模板串第 i 个字母与主串对应字母不匹配时,模板串下一个要与主串对应字母匹配的位置为 j
含义2. next[i] = j, 表示 t[1, j - 1] = t[i - j + 1, i - 1], 即以 i 结尾的最长公共前后缀的长度为 j - 1

C ++ 代码2

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1000010;

char s[N], t[N];
int ne[N];
int n, m;

void get_next(int next[]){
    int i = 1, j = 0;
    ne[1] = 0;
    while(i <= n){
        if(j == 0 || t[i] == t[j]) ++ j, ++ i, ne[i] = j;
        else j = ne[j];
    }
}

void kmp(char s[], char t[]){
    int i = 1, j = 1;
    while(i <= m && j <= n){
        if(j == 0 || s[i] == t[j]) ++ i, ++ j;
        else j = ne[j];
        if(j > n){
            cout << i - n - 1 << ' ';
            j = ne[j];
        }
    }
}

int main(){
    cin >> n >> t + 1 >> m >> s + 1;
    get_next(ne);
    // for(int i = 1; i <= n ; i ++) cout << ne[i] << endl;
    kmp(s, t);
    return 0;
}

C ++ 代码3

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1000010;

char s[N], t[N];
int ne[N];
int n, m;

//改进后的next函数
void get_next(int next[]){
    int i = 1, j = 0;
    ne[1] = 0;
    while(i <= n){//得包括计算ne[n + 1]的值, 
        if(j == 0 || t[i] == t[j]){
            ++ j, ++ i;
            if(t[i] != t[j]) ne[i] = j;
            else ne[i] = ne[j];
        }
        else j = ne[j];
    }
}

void kmp(char s[], char t[]){
    int i = 1, j = 1;
    while(i <= m && j <= n){
        if(j == 0 || s[i] == t[j]) ++ i, ++ j;
        else j = ne[j];
        if(j > n){
            cout << i - n - 1 << ' ';
            j = ne[j];
        }
    }
}

int main(){
    cin >> n >> t + 1 >> m >> s + 1;
    get_next(ne);
    // for(int i = 1; i <= n + 1 ; i ++) cout << ne[i] << ' ';
    kmp(s, t);
    return 0;
}