蓝桥杯KMP总结

本文给出了详解KMP原理的文章链接，以及蓝桥杯题单，并给出KMP模版题的题解。

目录

原理详解

KMP题单

KMP题解

小蓝的字符串（模版题）

题目描述

输入描述

输出描述

输入输出样例

求解方法一

求解方法二

---

原理详解

KMP算法（研究总结，字符串） - SYCstudio - 博客园 (cnblogs.com)

KMP题单

1203：小明的字符串

1628：最短循环节问题

1071：串的前缀

KMP题解

小蓝的字符串（模版题）

题目描述

小明有两个字符串，分别为 S,T。

请你求出 T 串的前缀在 S 串中出现的最长长度为多少。

输入描述

输入包含两行，每行包含一个字符串，分别表示 S,T。

1≤∣S∣,∣T∣≤10^6，保证 S,T 只包含小写字母。

输出描述

输出共 11 行，包含一个整数，表示答案。

输入输出样例

示例 1

输入

aabba
abb

输出

3

示例 2

输入

aabba
aba

输出

2

求解方法一

对每个T的前缀找S，暴力法（通过）。

s=input()
t=input()
ans=0
for i in range(len(t),0,-1):
    c=t[:i]
    if s.find(c)!=-1:
        ans=max(ans,i)
print(ans)

求解方法二

KMP。

N=100005
ne=[0]*N
 
def get_next(p):
    for i in range(1,len(p)):
        j=ne[i]
        while j and p[j]!=p[i]:
            j=ne[j]
        if p[j]==p[i]:ne[i+1]=j+1
        else:ne[i+1]=0
 
def kmp(s,p):
    ans=0
    j=0
    get_next(p)
    for i in range(len(s)):
        while j and p[j]!=s[i]:
            j=ne[j]
        if p[j]==s[i]:
            j+=1
            ans=max(ans,j)
        if ans==len(p): return ans
    return ans
 
s=input()
t=input()
print(kmp(s,t))