今天学了KMP算法

一开始没听懂
后来研究了一下
发现KMP效率好快！！！
（O(n+m)可不是吹的）

#include<iostream>
using namespace std;
//主字符串，要寻找的子串； 
string a,b;
//用于记录 相同前后缀长度；
int nxt[1919810];/*主意：next 是 关键词，不能 
做为 变量名，否则 会CE!!!*/ 
//主指针，子指针；
int z=0,zz=0;
//构建 next数组； 
void build_next(string str){
    //记录 当前的 相同前后缀长度；
    int len=0;
    //长度为1时 必然 没有 相同前后缀；
    nxt[0]=0; 
    //遍历 一遍 要寻找的子串；
    for(int i=1;i<str.size();i++){
        //若前缀 与 后缀 相同；
        if(str[len]==str[i]){
            //相同前后缀 长度+1；
            nxt[i]=++len;
            //记录； 
        }else{//否则； 
            //若 当前没有 相同前后缀； 
            if(len==0){
                //本身 没有 相同前后缀 
                nxt[i]=0;
            }else{//否则；
                //将 当前前后缀长度 设为 次长（上一个）前后缀长度；
                len=nxt[len-1];
                //重新判断； 
                i--;
            }
        } 
    }
}
int main(){
    //输入 两个 字符串； 
    cin>>a>>b;
    //构建 next数组(on line 11)； 
    build_next(b);
    //初始化 双指针；
    z=0;zz=0;
    //用 主指针 遍历 一遍 主字符串； 
    while(z<a.size()){
        //若 匹配； 
        if(a[z]==b[zz]){
            //双指针 前进； 
            z++;zz++;
        //否则 若 不是在 第一个字符处 失配； 
        }else if(zz>0){ 
            //重新匹配 失配的 字符； 
            zz=nxt[zz-1];
            /*重点：不 重新匹配 非失配的 字符*/
            /*
            相当于:
             ↓
            sawasaijdnawad
             awad
                ↑
            变为:
               ↓（前进）
            sawasaijdnawad
               awad
                ↑（不动）
            */
        }else{//否则（必然 在第一个字符处 失配）； 
            z++;
        }//主指针 前进； 
        //若 子指针 已经将 要寻找的子串 遍历完毕； 
        if(zz==b.size()){
            printf("%d\n",z-zz+1);
        }//则 输出 已匹配位置的 开头；
    }
    for(int i=0;i<b.size();i++){
        printf("%d ",nxt[i]);
    }//输出next数组； 

    return/*完毕*/0;
}
<z
nz

给蒟蒻点个赞吧QwQ