串模式匹配算法

# include <string.h># include <stdio.h># include <stdlib.h># define OK 1 # define ERROR 0 typedef int Status//串的定长顺序存储结构 # define MAX_STR_LEN 40 typedef char SString[MAX_STR_LEN + 1]//0号单元存放串的长度 Status StrAssign(SString T,char * chars)//生成一个其值等于chars的串T { int i if (strlen(chars) >MAX_STR_LEN) { return ERROR } else { T[0] = strlen(chars) for (i=1i<=T[0]++i) {T[i] = * (chars + i - 1) } return OK } } //返回串S的元素的个数 int StrLength(SString S) { return S[0]} //用Sub返回串S的自第pos个字符起长度为len的子串 Status SubString(SString Sub,SString S,int pos,int len) { int i if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1) { return ERROR } for (i=1i<=len++i) { Sub[i] = S[pos+i-1] } Sub[0] = len return OK} //输出字符串T void StrPrint(SString T) { int i for (i=1i<=T[0]++i) { printf("%c ",T[i]) } printf("\n")} //求模式串T的next函数值并卖者存入数组next void get_next(SString T,int next[]) { int i = 1,j = 0 next[1] = 0 while (i <T[0]) { if (j==0 || T[i]==T[j]) {++i ++j next[i] = j } else {j = next[j] } } } //求空配州模式串T的next函数修正值并存入数组nextval void get_nextval(SString T,int nextval[]) { int i = 1,j = 0 nextval[1] = 0 while (i <T[0]) { if (j==0 || T[i]==T[j]) {++i ++j if (T[i] != T[j]){ nextval[i] = j }else{ nextval[i] = nextval[j] } } else {j = nextval[j] } } } //利用模式串T的next函数求T在主串S中第pos字符之后的位斗蔽置的KMP算法 //1=<pos=<StrLength(S) int Index_KMP(SString S,SString T,int pos,int next[]) { int i = pos,j = 1 while (i<=S[0] &&j<=T[0]) { if (j==0 || S[i]==T[j]) {++i ++j } else {j = next[j] } } if (j >T[0]) { return i - T[0] } else { return 0 } } int main(void) { int i,* p SString s1,s2 StrAssign(s1,"aaabaaaab") printf("主串为：") StrPrint(s1)StrAssign(s2,"aaaab") printf("子串为：") StrPrint(s2) p = (int *)malloc((StrLength(s2) + 1) * sizeof(int)) get_next(s2,p) printf("子串的next的数组为：") for (i=1i<=StrLength(s2)++i) { printf("%d ",* (p+i)) } printf("\n") i = Index_KMP(s1,s2,1,p) if (i) { printf("主串和子串在第%d个字符处首次匹配\n",i) } else { printf("主串和子串匹配不成功\n") } get_nextval(s2,p) printf("子串的nextval数组为：") for (i=1i<=StrLength(s2)++i) { printf("%d ",* (p+i)) } printf("\n") printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p)) printf("求串s1的从第5个字符起长度为5的子串s2:\n")SubString(s2,s1,5,5) printf("串s2为:") StrPrint(s2) return 0} /* 在vc++6.0中的输出结果： ------------------------ 主串为：a a a b a a a a b 子串为：a a a a b 子串的next的数组为：0 1 2 3 4 主串和子串在第5个字符处首次匹配 子串的nextval数组为：0 0 0 0 4 主串和子串在第5个字符处首次匹配 求串s1的从第5个字符起长度为5的子串s2: 串s2为:a a a a b Press any key to continue ------------------------------ */

#include<iostream>

using namespace std

void Next(char T[],int next[])

{ next[0]=-1

int j=0,k=-1

while(T[j]!='扮祥\0')

if((k==-1)||(T[j]==T[k]))

{ j++

k++

next[j]=k

}

else k=next[k]

}

int KMP(char S[],char T[])

{ int i=0,j=0

int next[10]

Next(T,next)

while((S[i]!='\0')&&(T[j]!='\0'))

{ if(S[i]==T[j]) {i++j++}

else j=next[j]

if(j==-1)

{ i++j++}

}

if(T[j]=='\0'塌桥) return(i-j+1)

else return 0

}

int main()

{ char a[100],b[100]

cout<<"please enter primary string :"

cin.getline(a,100)

cout<<"please enter substring:"

cin.getline(b,100)

if(KMP(a,b)==0)

cout<<"not exist!\n"

else cout<厅衫搏<"location is:"<<KMP(a,b)<<endl

return 0

}

具体的你自己看吧。

本文主要讲述了串的模式匹配算法，包括BF算法、RK算法、KMP算法、BM算法，使用不同的算法实现目标串查找子串，重点在于分析的过程，通过不同的算法分析提高逻辑思维能力

模式匹配的目的就是在目标串中查找与模式串相等的子串。在这里称呼主串为s，模式串为t，主串的长度为n，模式串的长度为m

暴力算法，将目标串和模式串的每个字符都进行一一比较。性能最差，但是使用最广，因为实现简单，而且在字符串较小的情况下耗费的性能也很小。

O(n*m)

RK算法把字符串比较问题，转换为了Hash值比较问题。

将模式串t的每个字符的比较改成了将串作为整体与目标串进行哈希值比较，这样就减少了比较次数

以前模式串与子串的比较需要比较每个字符，现在只要整体比较依次哈希值就可以。所以减少了比较次数。

哈希算腔枣法

这里我们可以发现一个Hash冲突问题，比如"abc"和"bc"的Hash值是一样的，因为最高位是伍携拆0。所以还需要进行哈希冲突算法。

哈希冲突算法：

利用前一个结果计算下一个哈希值

这是因为目标串的相邻子串，其实相差的只有第一个字符隐竖和最后一个字符，其他字符是相同的，

所以我们可以利用前一个计算结果减去前一个字符串的第一个字符串，加上这个字符串的最后一个字符就够了。

针对BF的弊端，在KMP算法中可以进行多字符的跳跃对比，以此来避免目标串的不必要回溯。

例子：

简单说明一下：

真子串：

匹配：

例如：目标串："abxabcabcaby"，模式串："abcaby"

模式串的最大真子串为ab,

我们在匹配时，发现目标串的子串abcabc与模式串的前字符都匹配，最后一个字符不匹配

所以就从目标串的abcabc的后面abc开始与模式串进行匹配，而不需要匹配前面的abc了。

也就是从上一个a字符直接跳跃到了下一个a字符，而不是从b字符开始。

会存在一种情况：

实现思想：

它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的三四倍。BM算法的原理很多复杂，比较难懂，学起来比较烧脑。

实现思想和KMP算法基本上是一样的，都是先计算模式串的真子串，之后再查找真子串的大小，当出现不匹配时，直接在真子串后进行匹配，区别于KMP算法，它是从后往前匹配的

这里比上面的KMP算法增加了一个坏字符规则，可以更快的跳跃，当然KMP算法本身也可以使用坏字符规则

坏字符规则

好后缀规则

---