KMP算法初接触


偶然发现了hihoCoder上提供了一个“hiho一下”的编程联系,感觉相对系统且比较基础,适合我这种啥都不会的-_-|||

hiho一下

发现的比较晚,已经到了第三周的题目。第三周是学习KMP算法。这是一个非常经典的字符串匹配算法。所谓字符串匹配,就是判断一串字符(原串)中是否存在一个特定的字符串(模式串)。最开始,参考了下述两篇文章,编写了算法。

字符串匹配的KMP算法

从头到尾彻底理解KMP(2014年7月版)

具体原理就先不写了,有时间再撸吧。

这是我的第一版程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <string>
#include "iostream"

using namespace std;

int theNumofPattern = 0;

void nextCal(string s, int next[]);
int kmpCal(string s, string t);

int main( )
{
    int theNumofTest = 0;
    string s;
    string t;
    cin >> theNumofTest;
    while (theNumofTest--)
    {
        cin >> t;
        cin >> s;
        int sLength = s.length();
        int tLength = t.length();
        int theLocation = 0;

        while (theLocation < sLength)
        {
            if (theLocation != 0)
            {
                s = s.substr(theLocation - tLength + 1, sLength);
            }
            theLocation = kmpCal(s, t);
            if (theLocation == s.length())
                break;
        }
        cout << theNumofPattern << endl;
        theNumofPattern = 0;
    }

    return 0;
}


int kmpCal(string s, string t)
{
    int sLength = s.length();
    int tLength = t.length();
    int next[10001];
    nextCal(t, next);
    int i = 0;
    int j = 0;
    while ((i < sLength) && (j < tLength))
    {
        if (s[i] != t[j])
        {
            i = i - next[j];
            j = 0;
        }
        else
        {
            i++;
            j++;
        }
    }
    if (j == tLength)
    {
    //  printf("%d\n", i-1);
        theNumofPattern++;
    }
    else
    {
    //  printf("%s\n", "none"); 
    }
    return i;
}

void nextCal(string s, int next[])
{
    int len = s.length();
    next[0] = 0;
    for (int i = 1; i < len; i++)
    {
        int k = next[i - 1];
        while (s[i] != s[k] && k != 0)
            k = next[k - 1];
        if (s[i] == s[k])
            next[i] = k + 1;
        else
            next[i] = 0; 
    }
    for (int i = 0; i < len; i++)
    {
        next[len - 1 - i] = next[len - 2 - i];
    }
    next[0] = -1;
}

在电脑上测试样例通过,于是马上提交代码,结果却Time Limit Exceeded。

看来自己编写的确实算法复杂度太差了。回头看了看,循环太多,但是却又无从下手修改。

后来经大神xmfbit指点,参考下面这篇博客重新编写了程序。

KMP算法详解

第二版程序如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <string>
#include "iostream"

using namespace std;

int theNumofPattern = 0;

void nextCal(string s, int *next);
void kmpCal(string s, string t, int next[]);

int main( )
{
    int theNumofTest = 0;
    string s;
    string t;
    int next[10001];
    cin >> theNumofTest;
    while (theNumofTest--)
    {
        cin >> t;
        cin >> s;
        nextCal(t, next);
        kmpCal(s, t, next);
    }

    return 0;
}

void nextCal(string s, int *next)
{
    next[0] = 0;
    int j = 0;
    int sLength = s.length();
    for (int i = 1; i < sLength; i++)
    {
        while ((j > 0) && (s[j] != s[i]))
            j = next[j - 1];
        if (s[j] == s[i])
        {
            j = j + 1;
        }
        next[i] = j;
    }
}

void kmpCal(string s, string t, int next[])
{
    int i = 0;
    int j = 0;
    int sLength = s.length();
    int tLength = t.length();
    for (i = 0; i < sLength; i++)
    {
        while ((j > 0) && (t[j] != s[i]))
            j = next[j - 1];
        if (t[j] == s[i])
            j = j + 1;
        if (j == tLength)
        {
            theNumofPattern++;
            //cout << i - tLength << endl;
            j = next[j - 1];
        }
    }
    cout << theNumofPattern << endl;
    theNumofPattern = 0;
}

程序简短了许多,测试成功后,提交代码。

AC了~

耗时241ms,果然要比自己瞎编的要强得多啊。

Comments !