模式匹配算法

暴力匹配算法

1. int Violentmatch(char* s, char* p)  
2. {  
3.     int sLen = strlen(s);  
4.     int pLen = strlen(p);  
5.     int ans = -1;  
6.   
7.     int i = 0;  
8.     int j = 0;  
9.     while (i < sLen && j < pLen)  
10.     {  
11.         if (s[i] == p[j])  
12.         {  
13.             //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++    
14.             i++;  
15.             j++;  
16.         }  
17.         else  
18.         {  
19.             //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0    
20.             i = i - j + 1;  
21.             j = 0;  
22.         }  
23.     }  
24.     if (j == pLen)  
25.     {  
26.         //匹配成功，返回模式串p在文本串s中的位置    
27.         ans =  i - j;  
28.     }  
29.     return ans;  
30. }  

KMP算法

• 现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
  • 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
  • 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]，模式串P相对于文本串S向右移动了至少1位（换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1）

1. int KMP(char* s, char* p, int n)  
2. {  
3.     int ans = -1;  
4.     int i = 0;  
5.     int j = 0;  
6.     int pLen = strlen(p);  
7.     while (i < n)  
8.     {  
9.         //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++  
10.         if (j == -1 || s[i] == p[j])  
11.         {  
12.             i++;  
13.             j++;  
14.         }  
15.         else  
16.         {  
17.             //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]  
18.             //next[j]即为j所对应的next值    
19.             j = next[j];  
20.         }  
21.         if (j == pLen)  
22.         {  
23.             ans = i - j;  
24.             break;  
25.         }  
26.     }  
27.     return ans;  
28. }  

 如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：

    也就是说，原字符串对应的各个前缀后缀的公共元素的最大长度表为（下简称《最大长度表》）：

 把next 数组跟之前求得的最大长度表对比后，不难发现，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。意识到了这一点，你会惊呼原来next 数组的求解竟然如此简单！

    换言之，对于给定的模式串：ABCDABD，它的最大长度表及next 数组分别如下：

    根据最大长度表求出了next 数组后，从而有

失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值

 求next 数组的代码如下所示：

1. void getNext(char* p,int next[])  
2. {  
3.     int pLen = strlen(p);  
4.     next[0] = -1;  
5.     int k = -1;  
6.     int j = 0;  
7.     while (j < pLen - 1)  
8.     {  
9.         //p[k]表示前缀，p[j]表示后缀  
10.         if (k == -1 || p[j] == p[k])   
11.         {  
12.             ++j;  
13.             ++k;  
14.             next[j] = k;  
15.         }  
16.         else   
17.         {  
18.             k = next[k];  
19.         }  
20.     }  
21. }  

感谢july大神