POJ3461 KMP 模板题

最近忙着考研复习，所以刷题少了。。

数据结构昨天重新学习了一下KMP算法，今天自己试着写了写，问题还不少，不过KMP算法总归是理解了，以前看v_JULY_v的博客，一头雾水，现在终于懂了他为什么要在算完next[]之后，所有值都减一了。。。。。。

为了顺便复习下C语言，就没有用C++写，而且写出来比较丑。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define LEN 100
 4 void getNext(int *next, char *pattern)
 5 {
 6     int len = strlen(pattern);
 7     next[0] = -1;
 8     int i = 0, j = -1;
 9     while(i < len)
10     {
11         if(pattern[i] == pattern[j] || j == -1)
12         {
13             ++i, ++j;
14             next[i] = j;
15             if(patter[i] == pattern[j])
16                 next[i] = next[j];
17         }
18         else
19             j = next[j];
20     }
21 }
22 
23 int KMP(char *str, char *pattern, int *next)
24 {
25     getNext(next, pattern);
26     int len1 = strlen(str), len2 = strlen(pattern);
27     int i = 0, j = 0;
28     while(i < len1 && j < len2)
29     {
30         if(str[i] == pattern[j] || j == -1)
31         {
32             i++, j++;
33         }else{
34             j = next[j];
35         }
36     }
37     if(j == len2)
38         return i-j;
39     return -1;
40 }
41 int main()
42 {
43     int next[LEN];
44     char str[LEN], pattern[LEN];
45     int n, index;
46     scanf("%d", &n);
47     while(n--)
48     {
49         scanf("%s%s", str,pattern);
50         index = KMP(str, pattern, next);
51         printf("%d
", index);
52     }
53     return 0;
54 }
55 
56 
57 /*
58 测试用例
59 3
60 abcabcbababcaba
61 ababcaba
62 abcabcbababcaba
63 ababcaba
64 abcabcbababcaba
65 ababcaba
66 
67 */

View Code

2017年12月11日08:54:05

今天再来看字符串匹配的时候，KMP又忘记了，现在知道的是：

　　对于短字符串来说，匹配的时候，会计算它的部分匹配表（即，前缀和后缀相同时，串的最大长度）

　　当匹配时，需要用已经移动了的长度 - 部分匹配长度

详细请看

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

class Solution(object):
    def BF_Match(self, haystack, needle):
        hlen = len(haystack)
        nlen = len(needle)

        if hlen >= nlen:
            for k in xrange(hlen - nlen + 1):
                i = k
                j = 0
                while i < hlen and j < nlen and haystack[i] == needle[j]:
                    i += 1
                    j += 1
                if j == nlen:
                    return k
                else:
                    continue
        return -1

    def pmt(self, needle):
        """
        PartialMatchTable
        :param needle: 
        """
        nlen = len(needle)
        prefix = [needle[:i+1] for i in xrange(len(needle)-1)]
        print prefix
        postfix = [needle[i+1:] for i in xrange(len(needle)-1)]
        print postfix

        intersection = list(set(prefix) & set(postfix))
        maxlen = 0
        for i in xrange(0,len(intersection)):
            if maxlen < len(intersection[i]):
                maxlen = len(intersection[i])
        if intersection:
            #print intersection,maxlen
            return maxlen
        return 0

    def kmp(self, haystack, needle):
        i = 0
        hlen = len(haystack)
        nlen = len(needle)
        while i < hlen-nlen+1:
            match = True
            for j in xrange(nlen):
                if haystack[i+j] != needle[j]:
                    match = False
                    break
            if match:
                return i
            if j:
                i += j - self.pmt(needle[:j])
            else:
                i += 1
        return -1


    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if len(haystack) >= 0 and len(needle) == 0:
            return 0

        if len(haystack) < len(needle):
            return -1

        for i in xrange(0, len(haystack)):
            tmpi = i
            cnt = 0
            for j in xrange(0, len(needle)):
                if(tmpi < len(haystack)) and haystack[tmpi] == needle[j]:
                    tmpi += 1
                    j += 1
                    cnt += 1
                    if len(needle) == cnt:
                        return i

        return -1

haystack = "aabaaabaaac"

#haystack = "ababcaababcaabc"


needle ="aabaaac"

s = Solution()
print s.kmp(haystack, needle)