关于KMP算法
字符串匹配算法，emmm，网上很多介绍，有兴趣的搜一搜就有了，直接上题吧~
问题 A: DS串应用--KMP算法
题目描述
学习KMP算法，给出主串和模式串，求模式串在主串的位置
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串
以此类推
输出
第一行输出第1个实例的模式串的next值
第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0
以此类推
样例输入
3
qwertyuiop
tyu
aabbccdd
ccc
aaaabababac
abac
样例输出
-1 0 0
5
-1 0 1
0
-1 0 0 1
8
问题 B: DS串应用--串替换
题目描述
给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串
本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那
可能需要考虑模式串和替换串长度不一致的情况
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串，第四行输入第1个实例的替换串
以此类推
输出
第一行输出第1个实例的主串
第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。
以此类推
样例输入
3
aabbccdd
bb
ff
aaabbbccc
ddd
eee
abcdef
abc
ccccc
样例输出
aabbccdd
aaffccdd
aaabbbccc
aaabbbccc
abcdef
cccccdef
问题 C: 串应用- 计算一个串的最长的真前后缀
题目描述
给定一个串，如ABCDAB，则 ABCDAB的真前缀有：{ A, AB,ABC, ABCD, ABCDA } ABCDAB的真后缀有：{ B, AB,DAB, CDAB, BCDAB } 因此，该串的真前缀和真后缀中最长的相等串为AB，我们称之为该串的“最长的真前后缀”。 试实现一个函数string matched_Prefix_Postfix(string str)，得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty
输入
第1行：串的个数 n 第2行到第n+1行：n个字符串
输出
n个最长的真前后缀，若不存在最长的真前后缀则输出empty。
样例输入
6
a
ab
abc
abcd
abcda
abcdab
样例输出
empty
empty
empty
empty
a
ab
问题 D: DS串应用—最长重复子串
题目描述
求串的最长重复子串长度。例如：abcaefabcabc的最长重复子串是串abca，长度为4。
输入
测试次数t
t个测试串
输出
对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.
样例输入
3
abcaefabcabc
szu0123szu
szuabcefg
样例输出
4
3
-1
╭( ′• o •′ )╭☞警察叔叔！就是这个人！悄咪咪改了题目
以下是绿色健康的代码 (ﾟ∀ﾟ)☞
#include<bits/stdc++.h>
using namespace std;
class myString{
private:
string mainstr;
int size;
void getnext(string p,int next[]){
int i=1;
next[0]=-1;
next[1]=0;
int j=0;
while(i<(int)p.length()){
if(j==-1||p[i]==p[j]){
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
int KMPFind(string p,int pos,int next[]){
int i=pos;
int j=0;
while(i<(int)mainstr.length()&&j<(int)p.length()){
if(j==-1||mainstr[i]==p[j]){
++i;
++j;
}
else
j=next[j];
}
if(j>=(int)p.length())
return i-j+1;
else
return -1;
}
public:
myString(){
size=0;
mainstr="";
}
~myString(){
size=0;
mainstr="";
}
void setval(string p){
mainstr="";
mainstr.assign(p);
size=(int)mainstr.length();
}
int KMPFindSubstr(string p,int pos){
int i;
int L=p.length();
int *next =new int[L + 1];
getnext(p,next);
/* for(i=0;i<L;i++)
cout<<next[i]<<" ";
cout<<endl;
*/
int v=-1;
v=KMPFind(p,pos,next);
return v;
}//模式串位置
void Changemainstr(int i,string s,string p){
int j;
int pl=(int)p.length();
int sl=(int)s.length();
string sub1=mainstr.substr(0,i);
string sub2=mainstr.substr(i+pl,(int)mainstr.length());
mainstr=sub1+s+sub2;
cout<<mainstr<<endl;
} //模式串替换
string matched_Prefix_Postfix(){
int L=(int)mainstr.length();
int *next =new int[L + 1];
getnext(mainstr,next);
int ans = next[size];
delete[]next;
if (ans <= 0)
return "empty";
return mainstr.substr(0, ans);
}//最长的真前后缀字串
int Maxsubstr(){
int L=(int)mainstr.length();
int *next =new int[L + 1];
getnext(mainstr,next);
int ans=INT_MIN;
for(int i=0;i<=L;i++)
ans=ans>next[i]?ans:next[i];
return ans;
}//最长重复字串(重叠)
};
int main(){
/* int t;
cin>>t;
while(t--){//模式串位置
string s;
cin>>s;
myString S;
S.setval(s);
string p;
cin>>p;
cout<<S.KMPFindSubstr(p,0)<<endl;
}*/
/*int t;
cin>>t;
while(t--){//模式串替换
string s;
cin>>s;
myString S;
S.setval(s);
string p;
cin>>p;
int index=S.KMPFindSubstr(p,0);
string ps;
cin>>ps;
cout<<s<<endl;
if(index==-1){
cout<<s<<endl;
}
else{
S.Changemainstr(index-1,ps,p);
}
} */
/*int t;
cin>>t;
while(t--){//最长的真前后缀字串
string s;
cin>>s;
myString S;
S.setval(s);
cout<<S.matched_Prefix_Postfix()<<endl;
} */
int t;
cin>>t;
while(t--){////最长重复字串(重叠)
string s;
cin>>s;
myString S;
S.setval(s);
int ans=S.Maxsubstr();
if(ans==0)
ans--;
cout<<ans<<endl;
}
}
多说两句
原本问题D是要求不重叠的最长重复字串，上面的代码求出来的是最长重复字串（重叠），因为用next数组来求真的太简单了，要求不重叠的比较复杂……懒得一匹_(:з」∠) _
给大佬递茶.jpg
o(*≧▽≦)ツ┏━┓
最长重复字串（不重叠），由不留名的╭( ′• o •′ )╭☞XXX大佬提供
蒟蒻瑟瑟发抖﹙ˊ_>ˋ﹚
#include <iostream>
using namespace std;
const int N=5000+15;
string s, p;
int n[N];
void getnext(const string& p){
n[0] = -1;
int k = -1, i = 0;
while(i < (int)p.size()){
if(k == -1 || p[k] == p[i]){
i++;
k++;
n[i] = k;
}else{
k = n[k];
}
}
}
int kmpMatch(const string& p, string& s){
int j = 0, i = 0;
int ret = 0;
while(i < (int)s.size()){
if(j == -1 || p[j] == s[i]){
i++;
j++;
}else{
j = n[j];
}
if(j == (int)p.size()){
ret++;
j = 0;
}
}
return ret;
}
bool check(string s, int len){
for(int i = 0; i < (int)s.size() - len; i++){
getnext(s.substr(i, len));
if(kmpMatch(s.substr(i, len), s) >= 2)
return true;
}
return false;
}
int main(){
int t;
cin >> t;
while(t--){
cin >> s;
int k = 1, r = (int)s.size();
int ans = -1;
while(k <= r){
int m = (k + r) >> 1;
if(check(s, m)){
ans = m;
k = m + 1;
}else{
r = m - 1;
}
}
cout << ans << endl;
}
return 0;
}
