831. 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开始**/
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 1000010;

char S[M], T[N];//主串和模式串

int ne[N];//模式串的next数组
int n, m;


/**方法一：brute-force暴力算法 朴素的模式匹配算法*/
int normalMatch(char* S, char* T, int pos)
{
    
    int i = pos;
    int j = 1;

    while(i <= m && j <= n)
    {
    
        if(S[i] == T[j])//如果匹配，i和j后移
            i++,j++;
        else
            i = i-j+2, j = 1;//如果不匹配，i回溯到i最开始的下一个位置，j回溯到1
    }
    if(j > n) return i - n;
    return 0;
}

/** 方法二： 计算模式串的next数组时， i为当前的字符的下标，只需要关注模式串中 1~i-1 位置中的相等的最大真前后缀的长度即可 next[i] = 最大真前后缀的长度 + 1; 注意C++里面不能用char存储int类型的值，char的存储范围是-128~127 改写了 严蔚敏版《数据结构》kmp获取next数组的代码，易于理解 **/
void get_next(char* T)
{
    
    int i, j;
    ne[1] = 0;//模式串的第一个位置的next值为0，标记无法再继续回溯
    for(i = 2; i <= n; i++)//从第二个位置开始计算next值
    {
    
        j = ne[i-1];//首先将j置为 i前一个位置会回溯到的位置
        while(j && T[i-1] != T[j])//当j可以回溯，并且T[i-1]跟需要回溯到的位置的字符比较时，如果不匹配，则j继续往前回溯
            j = ne[j];
        ne[i] = j+1;//j是当模式串在i位置不匹配时，需要回溯到的下标，也刚好等于最大真前后缀的长度 next[i] = 最大真前后缀的长度 + 1;
    }
}

/**严蔚敏版《数据结构》kmp匹配过程*/
//S为主串 T为模式串 pos为开始查询的下标
int kmp(char* S, char* T, int pos)
{
    
    int i, j;
    i = pos;//主串从pos开始
    j = 1;//模式串从1开始

    while(i <= m && j <= n)
    {
    
        if(j == 0 || S[i] == T[j])//如果j回溯到了0 或者 模式串回溯到的位置的字符 与 主串当前字符 匹配， i和j则后移
            i++, j++;
        else
            j = ne[j];//如果模式串回溯到的位置的字符 与 主串当前字符 不匹配， 则j回溯到next[j]
    }

    if(j > n)//匹配完成后，如果匹配成功，那么j会走到 T[0]+1 i也会走到匹配完成的后面的一个位置
        return i - n;
    return 0;
}




int main()
{
    
    cin>> n >> T+1 >> m >> S+1;

// get_next(T);
//
// //题目数据范围较为严格，会超时
// for(int i = 1; i <= m; i++)
// {
    
// int tmp = kmp(S,T,i);
// if(tmp == 0)
// break;
// else
// i = tmp;
// cout<<tmp-1<<' ';
// }

    /**方法三：需要注意这种方法计算next数组的结果与严蔚敏版《数据结构》获取next数组的结果不同**/
    /**获取next数组，i从2开始**/
    ne[1] = 0;                       //下标为1的字符对应的next数组值固定为0
    int i, j;
    for(i = 2, j = 0; i <= n; i++)   //遍历模式串，从下标为2开始计算next值
    {
    
        while(j && T[i] != T[j+1])    //如果j不为0 并且将i跟j+1位置的字符进行匹配，能够匹配成功的情况，一定是以i为末尾的后缀，跟以j+1为末尾的前缀匹配成功，这前后缀一定是最大真前后缀，因为是前后缀是从串的前往后逐个判断的
            j = ne[j];                //如果i跟j+1位置的字符不匹配，则j一直回溯，每回溯一次，就比较一次i跟j+1位置的字符是否匹配
        if(T[i] == T[j+1]) j++;       //如果j为0 并且 当前i位置的字符跟第一个字符不匹配，则j一直为0；如果i跟j+1位置的字符匹配，则前后缀的字符长度自增，即模式串所指字符下标j自增
        ne[i] = j;                    //将当前i需要回溯到的下标j赋值给当前的next数组
    }

    /**kmp匹配过程，i从1开始**/
    for(i = 1, j = 0; i <= m; i++)
    {
    
        while(j && S[i] != T[j+1])//当主串i位置跟模式串的j+1位置字符不匹配时，模式串的j一直回溯，直到j回溯到下标为0(首字符的前一个位置) 或者 回溯到满足最大前后缀刚好匹配的位置
            j = ne[j];
        if(S[i] == T[j+1]) j++;   //如果主串的i位置跟模式串的j+1位置匹配，即最大真前后缀匹配时，j往后移动一个位置，i在循环中也会往后移动一个位置，则下次循环继续判断下一个i跟j+1是否匹配
        if(j == n)                //到达这一步，一定时j+1跟i位置字符匹配，并且j已经到达模式串的最后一个字符
        {
    
            cout<<i-n<<' ';      //因为题目是输出下标为0开始，所以是输出 i-模式串长度
            j = ne[j];           //当一次主串和模式串匹配完成后，i由于for循环一定会移动到跟模式串刚好匹配的下一个字符
                                 //j原本是在模式串的最后一个字符，将j赋值为ne[j]，目的是下次循环继续判断 以i-1为末尾的后缀的串的下一个字符 是否跟 以ne[j]为末尾的前缀的下一个字符匹配
        }
     }

    return 0;
}