在学习了 kmp算法 之后， 我想尝试y总的kmp模板能否实现对纯汉字字符串的关键词检索，经过尝试后居然不行。
随后尝试后发现一个汉字是占三个字节的，而模板题的输入只有数字和大小写字母，而数字和大小写字母是只占一个字节的强行套用当然不行啦hh。
要对模板进行稍稍地变形，才能实现我想要的功能。

首先讲一些前置知识

1.一个汉字占三个字节
2. `string z="这";` `(z[0]+z[1]+z[2])=="这"`
3.kmp算法的流程是先预处理模板字符串，得到next数组。随后将模板串与模式串进行匹配。

本篇博客可能要下面理解y总的kmp模板才能理解

贴上模板题的ac代码方便理解

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];//最长前后缀 前缀与后缀相同的最大长度
char s[M], p[N];
int main(){
    cin >> n >> p + 1 >> m >> s + 1;
//字符串下标从1开始
    for (int i = 2, j = 0; i <= n; i ++ ){
//ne[1]=0,所以i从2开始，递归求ne数组
//ne数组存放的是 当s[i]与p[j+1]不匹配时
//j回退成ne[i]中存放的下标值后 p[1~j]也能与上方的模式串s对应的 下标值
//缩句 ne存的是下标值
        while (j && p[i] != p[j + 1]) j = ne[j];
//求ne数组 我们用递归的方法求 
//当j不为0时 如果p[i]与p[j+1]不匹配下标就回退到ne[j]继续比较
        if (p[i] == p[j + 1]) j ++ ;
//匹配了的话 j++;因为后面赋值是ne[i]=j
        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 == n){
//j==n说明比较完了并且匹配
            printf("%d ", i - n);
            //输出下标
            j = ne[j];
            //j回退一下继续匹配新的情况
        }
    }
    return 0;
}

下面开始分段介绍代码

先看主函数

这里使用string存字符串，字符串的开头的加入一个汉字，以实现和模板一样的字符串从下标1开始存起的。
输入顺序是先输入模板串p的长度和模板串p 在输入模式串s的长度和模式串s
随后写了个函数kmps来实现kmp的流程

int main (){
    string s,p,u;
    s=p="啥";//字符串的开头的加入个字符，以实现和模板一样的字符串从下标1开始存起的。
    cin>>n>>u;p+=u;
    cin>>m>>u;s+=u;
    kmps(n,p,m,s);
    return 0;
}

接下来介绍kmps函数

kmps调用了两个函数
分别是bc和check1
其中bc是实现返回一个汉字的功能 目的是为了使代码便于调试

string bc(string &p,int x){//转换函数 返回一个字符串 实际上为一个汉字
    return p.substr(x*3,3);//一个汉字占三个字节嘛
}

check1函数是对模板串进行预处理 求出next数组 在本篇博客的代码中ne就是流程中的next数组

void check1(int n,string &p){//kmp算法的预处理步骤 求模板串的next数组
    for (int i=2,j=0;i<=n;i++){
        while (j&&bc(p,i)!=bc(p,j+1))j=ne[j];
        if (bc(p,i)==bc(p,j+1)) j++;
        ne[i]=j;
        //cout<<ne[i]<<' ';
    }
}

与模板题的预处理流程进行对比

//模板题的预处理流程
    for (int i=2,j=0;i<=n;i++){
        while (j&&p[i]!=p[j+1]) j=ne[j];
        if (p[i]==p[j+1]) j++;
        ne[i]=j;
        //cout<<ne[i]<<' ';
    }

最后看看kmps函数内部

首先kmps参数n，m分别是模板串p与模式串s的长度
也可以这么说字符串p是关键词 s是待检索的正文 n，m分别是关键词和正文的长度

void kmps(int n,string &p,int m,string &s){
    check1(n,p);//调用check1函数预处理出next数组
    for (int i=1,j=0;i<=m;i++){
        while (j&&bc(s,i)!=bc(p,j+1)) j=ne[j];
        if (bc(s,i)==bc(p,j+1)) j++;
        if (j==n){
            printf ("%d ",i-n);//输出关键词出现位置的起始下标（下标从 0 开始计数）
            j=ne[j];//与模板题的输出格式一致
        }
    }    
}

至此本篇博客结束 下面贴上完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int ne[N],n,m;
string bc(string &p,int x);//转换函数 返回一个字符串 实际上为一个汉字
void check1(int n,string &p);//kmp算法的预处理步骤 求模板串的next数组
void kmps(int n,string &p,int m,string &s){
    check1(n,p);//调用check1函数预处理出next数组
    for (int i=1,j=0;i<=m;i++){
        while (j&&bc(s,i)!=bc(p,j+1)) j=ne[j];
        if (bc(s,i)==bc(p,j+1)) j++;
        if (j==n){
            printf ("%d ",i-n);//输出关键词出现位置的起始下标（下标从 0 开始计数）
            j=ne[j];//与模板题的输出格式一致
        }
    }    
}
int main (){
    string s,p,u;
    s=p="啥";//字符串的开头的加入个字符，以实现和模板一样的字符串从下标1开始存起的。
    cin>>n>>u;p+=u;
    cin>>m>>u;s+=u;
    kmps(n,p,m,s);
    return 0;
}
string bc(string &p,int x){//转换函数 返回一个字符串 实际上为一个汉字
    return p.substr(x*3,3);//一个汉字占三个字节嘛
}
void check1(int n,string &p){//kmp算法的预处理步骤 求模板串的next数组
    for (int i=2,j=0;i<=n;i++){
        while (j&&bc(p,i)!=bc(p,j+1))j=ne[j];
        if (bc(p,i)==bc(p,j+1)) j++;
        ne[i]=j;
        //cout<<ne[i]<<' ';
    }
}