时间戳

首页 > 技术文章 > KMP算法

KMP算法

dominjune 2015-08-09 17:40 原文

第一次用繁體字寫裝一下逼...

KMP算法是一種改進的字符串匹配算法。KMP算法的關鍵是利用匹配失敗後的信息，儘量減少模式串與主串的匹配次數以達到快速匹配的目的。

具體的實現就是實現一個next函數，函數本身包含了模式串的局部匹配的信息。當然我還不是很懂的...

第一步是得到next數組，next[i]代表的是當前位置i字符跳的步長，就是跳回去下一步應該進行的匹配的位置;

第二步根據next數組找到匹配的位置，一般找到第一個就好了，當然也可以找出一共有多少個匹配的，貌似功能挺多的...

來几題:

poj 3461.Oulipo

通過KMP算法找出模式串在主串中出現的個數：

 1 // poj 3461.Oulipo
 2 // KMP算法 统计子串匹配次数 
 3 
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <algorithm>
 8 
 9 using namespace std;
10 
11 int n;    //目标串长度 
12 int m;    //源串长度 
13 char t[10005];    //目标串 
14 char s[1000005];    //源串 
15 int next[10005];    //next数组 
16 
17 void get_next()
18 {
19     int i = 0, j = -1;
20     next[0] = -1;
21     while(i < n)
22     {
23         if(j == -1 || t[i] == t[j])        //对目标串处理得到next数组 
24         {
25             i++, j++;
26             next[i] = j;
27         }
28         else
29             j = next[j];
30     }
31 }
32 
33 int KMP()
34 {
35     int count = 0;
36     get_next();
37     int i=0, j=0;
38     while(i != m)
39     {
40         if(j == -1 || s[i] == t[j])
41             i++, j++;
42         else
43             j = next[j];
44         if(j == n)
45         {
46             count++;        //每次找到匹配的子串，count++; 
47             j = next[j];
48         }
49     }
50     if(count == 0)
51         return 0;    //匹配失败 
52     return count;
53 }
54 
55 int main()
56 {
57     int k;
58     scanf("%d", &k);
59     while(k--)
60     {
61         memset(next, 0, sizeof(next));
62         scanf("%s", t);
63         scanf("%s", s);
64         n = strlen(t);
65         m = strlen(s);
66         int ans = KMP();
67         printf("%d\n", ans);
68     }
69     return 0;
70 }

 

接下來這題可以更好的加深對next數組的理解：

poj 2406.Power Strings 

很奇怪要用G++編譯才能過...

// poj 2406.Power Strings
// KMP算法　找出組成主串的重複子串
// e.g. abababa -> ab 
// references:
// http://blog.sina.com.cn/s/blog_6635898a0100l3sd.html
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000005;

char s[N];
int next[N];
int len;

int get_next()
{
    int i = 0, j = -1;
    next[0] = -1;
    while(i < len)
    {
        if(j == -1 || s[i] == s[j])
        {
            i++, j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int main()
{
    while(scanf("%s", s) != EOF)
    {
        if(s[0] == '.')
            break;
        len = strlen(s);
        get_next();
        int ans = 1;
        if(len % (len - next[len]) == 0)
            ans = len / (len - next[len]);
        printf("%d\n", ans);
    }
    return 0;
}

 

poj 1961.Period 

跟上一題一樣的，只是輸出不同；這題輸出第幾個位置出現來多少次子串，舉個栗子：

aabaabaabaab... 

輸出

3　1　表示到第三個位置出現一個aab，就是這麼簡單！！！

 1 // poj 1961.Period
 2 // KMP算法 poj 2406的加強版而已  
 3 // references:
 4 // http://blog.csdn.net/niushuai666/article/details/6967716
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 
10 using namespace std;
11 
12 const int N = 1000005;
13 
14 char s[N];
15 int next[N];
16 int len;
17 
18 int get_next()
19 {
20     memset(next, 0, sizeof(next));
21     int i = 0, j = -1;
22     next[0] = -1;
23     while(i < len)
24     {
25         if(j == -1 || s[i] == s[j])
26         {
27             i++, j++;
28             next[i] = j;
29         }
30         else
31             j = next[j];
32     }
33 }
34 
35 int main()
36 {
37     int k=1;
38     while(scanf("%d", &len) != EOF, len)
39     {
40         scanf("%s", s);
41         get_next();
42         int ans = 1;
43         int count = 0;
44         printf("Test case #%d\n", k++);
45         for(int i=1; i<=len; i++)
46         {
47             if(i % (i - next[i]) == 0)
48             {
49                 ans = i / (i - next[i]);
50                 if(ans != 1)
51                     printf("%d %d\n", i, ans);
52                 
53             }        
54         } 
55         printf("\n");
56     }
57     return 0;
58 }

 

一次過三題，你值得擁有！！！

 

推荐阅读