蓝桥杯KMP总结_小蓝的字符串约束难题-CSDN博客

本文链接：https://blog.csdn.net/HP_C2H2/article/details/130905105

本文详细介绍了KMP算法的原理，并提供了蓝桥杯比赛中的相关题目，包括1203题小明的字符串和1628题最短循环节问题。通过实例展示了如何使用KMP算法解决字符串的前缀匹配问题，同时给出了暴力法的解决方案作为对比。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

本文给出了详解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

输出

示例 2

输入

aabba
aba

输出

求解方法一

对每个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))