关于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;
}