字符串匹配

1.朴素算法(BruteForce)

代码：

 1 int AlmostBruteForce(string Text, string Pattern)  
 2 {  
 3     int lenT = Text.length();  
 4     int lenP = Pattern.length();  
 5 
 6     int s,i;  
 7     for (s = 0; s <= lenT-lenP; s++)  
 8     {  
 9         i = 0; //回溯 
10         bool bEqual = true;  //每一次都置true
11         while (bEqual && (i < lenP))  
12         {  
13             if (Text[s+i] == Pattern[i])  
14             {  
15                 i++;  
16             }  
17             else  
18             {  
19                 bEqual = false;  
20             }  
21         }  
22 
23         if (bEqual)  
24         {  
25             return s;  
26         }  
27     }  
28 
29     return -1;  
30 }

View Code

2.kmp算法：

（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。

（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。

如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]

（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。

即T[0]T[1]T[2]。。。T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1] ，且T[j] != T[k].（1≤k<j）;

(4) next[j]=0 意义：除（1）（2）（3）的其他情况。

next函数生成代码：

 1 voidgetNext(constchar*pattern,intnext[])
 2 {
 3     next[0]=-1;
 4     int k=-1,j=0;
 5     while(pattern[j]!='\0')
 6     {
 7         while(k!=-1&&pattern[k]!=pattern[j])k=next[k];
 8         ++j;
 9         ++k;
10         if(pattern[k]==pattern[j])
11         next[j]=next[k];
12         elsenext[j]=k;
13     }
14 }

View Code

参考：http://blog.csdn.net/zlhy_/article/details/8655349

http://baike.baidu.com/link?url=QhM2pQuJ7g5nWYx06634LXC-X2M76l6c7HSeFIo0r3Zsju-flND8vbTJseLK4WFi

http://blog.chinaunix.net/uid-27164517-id-3280128.html

字符串匹配

推荐阅读