今天将开启新的篇章，关于字符串的学习和练习，今天将给大家详细介绍一下KMP算法的思路。

KMP算法是用来匹配字符串长度的算法，可以将O（n2）的时间复杂度变为O（n）。

这里有几个注意点：

1.首先是注意next数组的构造，通过前后缀的方式进行构造。next数组只与）有关，用自己匹配自己。

2.匹配next数组

p模式串求next数组模版：

模式串匹配：

问题描述

给定一个长度为 n 的字符串 S ，幸运字符串的定义如下：

1. 该字符串为 S 的一个前缀字符串 。
2. 该字符串在 S中至少出现过 2 次 。

现在要你求出长度最大的幸运字符串 。

输入格式

输入第一行，包含一个整数 n ，表示字符串的长度 。

输入第二行，长度为 n 且由小写字母组成的字符串 。

输出格式

输出仅一行，包含一个整数，表示长度最大的幸运字符串的长度 。

输入案例：

9
abcdaaaba

输出案例：

2

代码部分：

#include <bits/stdc++.h>
const int N=2e5+10;
using namespace std;
char T[N];
int nex[N];
void get_next(int n,char *s){nex[0]=nex[1]=0;for(int i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1])j=nex[j];if(s[i]==s[j+1])j++;nex[i]=j;}
}
int main()
{int n;cin>>n;cin>>T+1;get_next(n,T);int ans=0;for(int i=1;i<=n;i++){ans=max(ans,nex[i]);}cout<<ans<<endl;return 0;
}

这道题就是最基本和简单kmp问题，大家可以拿这道题做为最基本的模版问题来记忆。

好了，今天的分享就到这里，希望大家多多关注，博主后续也会继续进行分享。