2023年7月20日发(作者：)

字符串匹配：求给定字符串的next数组以及KMP算法⼀. 理解字符串的next数组值next数组值的概念涉及到字符串匹配的问题，⽐较抽象，先介绍⼀些预备知识：1. 主串和模式串 例如我们想知道⼀个字符串是否包含另⼀个字符串时，如串S="bbc abcdab abcdabcdabde"中是否包含串s="abcdab"，那么S称为主串，s称为模式串。解决这个字符串匹配问题的算法就是KMP算法。KMP算法与next数组关系密切。有关KMP算法：。1.1 字符串的前缀和后缀给定字符串"bread", 前缀：是指除最后⼀个字符外，剩余字符的全部头部组合。"b,br,bre,brea",共有四个元素。 后缀：是指除第⼀个字符外，剩余字符的全部尾部组合。"read,ead,ad,d"，共有四个元素。1.2 字符串的前缀和后缀的最⼤长度 含义：前缀和后缀相同元素的最⼤长度。举例说明如下：以变量S表⽰ABCDAB,下⾯是S的各个⼦串 A：前缀和后缀都是空集，没有相同元素，长度为0 AB：前缀[A],后缀是[B],没有相同元素，长度为0 ABC:前缀是[A, AB],后缀是[BC, B]，长度为0ABCD:前缀是[A, AB, ABC],后缀是[BCD, CD, D]，没有相同元素，长度为0ABCDA:前缀是[A, AB, ABC,ABCD],后缀是[BCDA, CDA, DA, A]，共同元素是[A],长度为1ABCDAB:前缀是[A, AB, ABC,ABCD, ABCDA],后缀是[BCDAB, CDAB, DAB, AB, B]，共同元素是[AB],长度为2因此，字符串变量S前缀和后缀的最⼤长度=22. next[j]=k数组 利⽤KMP算法将模式串从第⼀个位置开始⾃坐向右移动逐个匹配主串时，当模式串第j个字符与主串第i个字符失配，为了提⾼匹配效率，避免回溯，将模式串在失配位置向右移动j-next[j]位，再继续匹配，j叫做已匹配值（0<=j#includeusing namespace std;//get the next array of pattern stringvoid getnext(string &p,int next[]){ int length=(); //int next[length]; int j=0,k=-1; //初始化next数组第⼀个值，k表⽰next数组的值，即失配字符j之前的⼦串中前缀和后缀最⼤的长度值 next[0]=-1; //计算next[j] while(j

//根据定义：k=next[k],p[k]==p[j]时，next[j+1]=next[k]+1, //且保证p[j+1]!=p[next[j+1]]则匹配成功,否则继续递归寻找 if (k==-1 || p[j]==p[k]) { j++; k++; if(p[j]!=p[k])//此时j=j+1，k=next[k]+1 next[j]=k; else next[j]=next[k]; } else k=next[k]; } //return next;}void main(){ string p="abc"; int * next = new int[()]; getnext(p, next); for(int i=0;i < (); i++) cout<#includeusing namespace std;//get the next array of pattern stringvoid getnext(string &p,int next[]){ int length=(); //int next[length]; int j=0,k=-1; //初始化next数组第⼀个值，k表⽰next数组的值，即失配字符j之前的⼦串中前缀和后缀最⼤的长度值 next[0]=-1; //计算next[j] while(j

//根据定义：k=next[k],p[k]==p[j]时，next[j+1]=next[k]+1, //根据定义：k=next[k],p[k]==p[j]时，next[j+1]=next[k]+1, //且保证p[j+1]!=p[next[j+1]]则匹配成功,否则继续递归寻找 if (k==-1 || p[j]==p[k]) { j++; k++; if(p[j]!=p[k])//此时j=j+1，k=next[k]+1 next[j]=k; else next[j]=next[k]; } else k=next[k]; } //return next;}//返回主串中模式串与其匹配成功时第⼀个字符位置int Kmpsearch(string &src,string &p,int k,int next[]){

//从主串的第k个字符开始搜索， int index_s = k, index_p = 0; int length_s = (); int length_p = ();

while(index_s < length_s && index_p < length_p) { if (index_p == -1 || p[index_p] == src[index_s]) { index_s++; index_p++; } //如果index_s != -1,且src[index_s] != p[index_p],即匹配失败，则令index_s保持不变，index_p=next[index_p]； else index_p = next[index_p]; } if (index_p==length_p) return index_s-index_p; else return -1;}void main(){ string src="abaacabcd",p="abc"; //cout<<"please input two string:"<>src; //cin>>p; int k=0;

int * next = new int[()]; getnext(p, next); for(int i=0;i < (); i++) cout<

参考⽂献：