KY91 String Matching

KY91 String Matching

版本一:暴力解法

"版本一:暴力解法"

import sys
for line in sys.stdin:
    line = line.strip()
    text, pattern = line.split(" ")
    cnt = 0
    while(True):
        pos = text.find(pattern)
        if pos != -1:
            cnt += 1
            text = text[pos+1:]
        else:
            break
    print(cnt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

KMP算法:

import sys

def getNext(pattern):
    length = len(pattern)
    assert length > 0
    next = [None] * length
    for pointer in range(length):
        if pointer == 0:  # 第一个位置取值恒为-1
            next[pointer] = -1
            continue
        else:
            if pattern[pointer] ==  pattern[next[pointer-1]+1]:  # 利用前一个位置的前后缀匹配关系判断下一个字符是否继续得到匹配
                next[pointer] = next[pointer-1] + 1  # 下一个字符仍然匹配,因此长度加1
            else:
                if next[pointer-1] == -1:  # 表示截止到前一个字符,没有前后缀匹配,而且从上一个if语句得知当前字符也未匹配
                    next[pointer] = -1  # 未得到匹配,取值为-1
                    continue  # 继续下一次循环,计算next数组的下一个取值
                scan = next[next[pointer-1]]  # 当前匹配失败后,考虑前一个位置的前后缀匹配关系
                while(True):  
                    if pattern[scan+1] == pattern[pointer]:  # 得到匹配
                        next[pointer] = scan + 1  # 找到匹配的前后缀
                        break  # 跳出while循环
                    else:
                        if scan == -1:  # 表示整个字符串中都未得到匹配,因此取值为-1
                            next[pointer] = -1  # -1表示未得到匹配
                            break
                        else:
                            scan = next[scan]  # 匹配失败,继续前溯
    return next  # 返回next数组



# KMP函数接收一个文本字符串text和一个模式字符串pattern,实现KMP算法
def KMP(text,pattern):  # 返回在文本字符串text中匹配子串的起始位置,若不匹配则返回None
    next = getNext(pattern)  # 获取next数组,列表类型
    length_txt = len(text)  # 获得文本字符串的长度
    length_pat = len(pattern)  # 获得模式字符串的长度
    ptr_txt, ptr_pat = 0, 0  # 初始化两个字符串的指针位置,或者理解为索引位置
    count = 0
    while(ptr_txt<length_txt and ptr_pat<length_pat):  # 循环遍历整个文本字符串
        if pattern[ptr_pat] == text[ptr_txt]:  # 字符获得匹配
            ptr_txt += 1  # 文本字符串的指针加1 
            ptr_pat += 1  # 模式字符串的指针加1
            if ptr_pat == length_pat:  # 判断是否对模式字符串遍历完成
                count += 1
                ptr_txt, ptr_pat = ptr_txt-ptr_pat+1, 0
                # return (ptr_txt - ptr_pat)  # 获得匹配,返回匹配的起始位置
            continue  # 当前字符串成功匹配,继续进行下一次比较
        else:
            if ptr_pat == 0:  # 模式字符串前溯到起始位置,仍旧未获得匹配的前缀后缀,因此将文本字符串指针向后移动
                ptr_txt += 1  # 文本字符串的指正位置向后移动,继续扫描两个字符串进行比较
            else:
                ptr_pat = next[ptr_pat-1] + 1  # 匹配失败之后前溯
    print(count)  # 整个文本字符串中都未出现模式字符串,匹配失败,返回未匹配的标志None
            


for line in sys.stdin:
    text, pattern = line.strip().split(" ")
    KMP(text,pattern)
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