2024.6.14刷题记录-KMP记录

目录

一、831. KMP字符串 - AcWing题库

1.普通版KMP

2.代码简洁版KMP

---

一、831. KMP字符串 - AcWing题库

1.普通版KMP

学习记录（http://t.csdnimg.cn/JxPv5）。解题代码如下：

# KMP算法
# 创建next数组
def build_next(patt):
    i = 1
    n = len(patt)
    prefix_len = 0
    next = [0] * n
    while i < n:
        if patt[prefix_len] == patt[i]:
            # 匹配成功，继续匹配后面的
            prefix_len += 1
            next[i] = prefix_len
            i += 1
        else:
            # 匹配失败
            if prefix_len == 0:
                # 匹配下一个
                # next.append(0)
                i += 1
            else:
                # 跳转
                prefix_len = next[prefix_len - 1]
    return next
    
patt_len = int(input())
patt = input()
string_len = int(input())
string = input()
next = build_next(patt)
 
# kmp搜索
i = 0
j = 0
ans = []
while i < string_len:
    if string[i] == patt[j]:
        i += 1
        j += 1
    elif j > 0:
        # 跳转
        j = next[j - 1]
    else:
        # 一点不匹配
        i += 1
    
    if j == patt_len:
        # 找到子串
        ans.append(i - j)
        j = next[j - 1]     # 注意这里是跳转
 
for x in ans:
    print(x, end = ' ')

2.代码简洁版KMP

来自题解（AcWing 831. KMP字符串 - AcWing）。通过在字符串前面加一空格，减少j==0这一判断条件。

# 代码更简洁版KMP
if __name__ == '__main__':
    patt_len = int(input())
    patt = ' ' + input()    # 使下标从1开始
    string_len = int(input())
    string = ' ' + input()
    next = [0] * (patt_len + 1)
    
    # next数组
    j = 0   # 匹配下标
    for i in range(2, patt_len + 1):    # 类似主串下标
        while j and patt[i] != patt[j + 1]:
            # 跳转
            j = next[j]
            
        if patt[i] == patt[j + 1]:
            # 匹配成功，匹配下标加一
            j += 1
            
        next[i] = j
        
    # 字符串匹配
    j = 0
    for i in range(1, string_len + 1):
        while j and string[i] != patt[j + 1]:
            j = next[j]
        
        if string[i] == patt[j + 1]:
            j += 1
        
        if j == patt_len:
            print(i - j, end = ' ') # i+1-j-1 = i-j
            j = next[j]

完

感谢你看到这里！一起加油吧！