串的模式匹配一、简单的模式匹配算法(BF算法)二、KMP算法
一、简单的模式匹配算法(BF算法) )
在实际应用中，也称为串这样的模式匹配、子串的定位操作。 例如单词检索、百度检索都是字符串的模式匹配操作。
在字符串模式匹配：主字符串中找到与模式字符串相同的字符串，然后返回到该位置。
串——主串的部分必须存在； 模式列——可以不定地在主列中找到。例如：主串为：‘abaabaabcabaa’，模式串：‘baabc’；算出串第个字符的位置。
【逻辑分析】计算：主串中有多少个部分串，匹配模式串和部分串； 子字符串和模式字符串从一开始就匹配，如果第一个字符串相等，然后与下一个字符串匹配，以确定模式字符串匹配成功还是失败，并返回结果。
子字符串： { abaab,baaba,aabaa,abaab,baabc,aabca,bcaba,cabaa}
模式列：baabc
(易知)匹配第5个子字符串时，匹配成功，返回子字符串第一个字符的位置。 在循环匹配中，模式列总是从第一个字符开始匹配。 另一方面，如果部分串的匹配不成功，则主串被重新匹配1。
在许多场景中，主字符串远远长于图案字符串，即nm。
匹配成功的最高时间复杂度3360o(m )；
匹配失败的最高时间复杂度：o(n-m1 )=o(n )=o(n )；
匹配失败的最坏时间复杂度： o(n*m )。
intindex(sstrings，SString T，int pos )//返回模式列t在主列s的pos字符后第s个出现的位置。 如果不存在，则返回值为0//，其中t不是空，而是1posstrlength(s ) int i=pos； int j=1； while(I=s.Lengthj=t.Length ) if ) s[I]==t[j] ) I； j； (//后续字符的else )继续比较I=I-j2； j=1； (//指针返回并重新开始匹配) if(JT.Length )返回I-t.length； elsereturn 0； } 完整代码：
/***字符串匹配算法* * */# include cstring # includeiostreamusingnamespacestd； # defineo k1 # define error0# define overflow-2 typedef int status； #define MAXSTRLEN 255 //用户可以在255内定义最长字符串长度typedef char SString[MAXSTRLEN 1]； 生成与存储在//0号单元格中的字符串长度statusstrassign(sstringt，char *chars ) chars相等的字符串Tint i； if(strlen ) chars ) MAXSTRLEN )返回错误器； else{t[0]=Strlen(chars )； //char的长度为t[0]for(I=1； i=T[0]； I ) t(I )=* ) charsI-1 )； //char的值被分配给字符串Treturn OK； //算法4.1 BF算法intindex(sstrings，SString T，int pos )//返回模式t出现在主串s中第pos字符之后的第s个位置。 如果不存在，则返回值为0//，其中t不是空，而是1posstrlength(s ) int i=pos； int j=1； wile(I=s[0]j=t[0] ) if ) s[I]==t[j] ) I； j； (//后续字符的else )继续比较I=I-j2； j=1； (/)指针后退并恢复匹配) if(jt[0] )返回I-t [0]； elsereturn 0； 返回0； }//Indexint main () {SString S； //S串为主串strassign(s，' abaabaabcabaa )； SString T； //T列为图案列； strassign(t，' baabc )； cout '主字符串和子字符串在第' index(s，t，1 ) '个字符中首次匹配(n )； 返回0； }
二、KMP算法之上的BF算法频繁重复的比较，相当于模式序列不断进行自我比较，效率低下。 我们必须考虑有没有更多的高中方法。
我们不想执行主字符串的回溯操作，而是利用部分匹配直接跳到还不匹配的字符处。
next数组：模式列的第j个字符匹配失败时，使模式列跳至next[j]继续匹配。
在部分字符串和模式字符串不一致的情况下，主字符串指针I不追溯，模式字符串指针j=next[j]。
KMP算法，最坏的时间复杂度o(mn )； 在此，求出next阵列的时间复杂度o[m]、模式匹配过程的最差时间复杂度o[n]。
/***字符串匹配算法* * */# include cstring # includeiostreamusingnamespacestd； # defineo k1 # define error0# define overflow-2 typedef int status； #define MAXSTRLEN 255 //用户可以在255内定义最长字符串长度typedef char SString[MAXSTRLEN 1]； 生成与存储在//0号单元格中的字符串长度statusstrassign(sstringt，char *chars ) chars相等的字符串Tint i； if(strlen ) chars ) MAXSTRLEN )返回错误器； else{t[0]=Strlen(chars )； for(I=1； i=T[0]； I ) t(I )=* ) charsI-1 )； 返回确定； }//next函数值voidget_next(sstringt，int next[] )//求出图案列t的next函数值，存储到数组nextint i=1，j=0中； next[1]=0； while(It[0] ) if(j==0||t[I]==t[j] ) /从模式列t中，选择next数组{ i； j； next[i]=j； }elsej=next[j]； }//get_next//KMP算法使用intindex_KMP(sstrings，SString T，int pos，intnext () /模式列t的next函数定位主列s中第pos字符之后的位置j； }else //利next数组进制匹配(主字符串指针不追溯) j=next[j]； //将模式列向右移动if (JT [0] )//匹配成功返回jt[0]； elsereturn 0； (}int main ) ) {SString S； strassign(s，' aaabbaba )； SString T； strassign(t，' abb ' )； int *p=new int[T[0] 1]； 生成//t的next数组get_next(t，p )； cout '主字符串和子字符串在第' index_kmp(s，t，1，p ) '个字符中首次匹配(n )； 返回0； }