ICPCG

 avatar
user_8384735
c_cpp
2 years ago
1.8 kB
7
Indexable
Never
// icpcG.cpp
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

void computeLPSArray(string pat, int M, int* lps)
{
    int len = 0;
 
    lps[0] = 0; 
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
bool KMPSearch(string pat, string txt)
{
    int M = pat.length();
    int N = txt.length();
    int lps[M];
    memset(lps, 0, sizeof(lps));
    computeLPSArray(pat, M, lps);
 
    int i = 0; // index for txt[]
    int j = 0; // index for pat[]
    while ((N - i) >= (M - j)) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
 
        if (j == M) {
            return true;
            //j = lps[j - 1];
        }
 
        else if (i < N && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return false;
}
string solve(string s) {
    int n = s.length(), maxi = 0;
    string ans;
    for (int i = 0; i < n; i++){
        for (int j = i; j < n / 2; j++){
            string t = s.substr(i, j);
            string s1 = s.substr(j + 1, n - 1);
            if (KMPSearch(t, s1)){
                if (maxi < t.length()){
                    ans = t;
                    maxi = t.length();
                }

            }
        }
    }
    return ans;
}
int main(){
    string s;
    cin >> s;
    cout << solve(s);
    //cout << s;
}