백준 1701번 : Cubeditor - KMP

https://www.acmicpc.net/problem/1701

1701번: Cubeditor

1. 문제설명

주어진 문자열 중에 두번이상 나오는 부분 문자열의 최대 길이를 구해야한다.

 

하나의 문자열에서 두번 이상 나오는 부분 문자열은

KMP알고리즘에서 prefix와 suffix를 비교하는 fail함수를 만드는 과정에서 구할 수 있다.

 

단 이때 이 문제에서 나올 수 있는 모든 prefix의 경우를 살펴야하기 때문에

for문을 한번 돌면서 시작지점을 정하고 그때마다 kmp fail함수를 만들어서 

가장 길게 매칭되는 prefix suffix의 길이를 구해야 한다.

 

 

2. 문제풀이코드

#include <iostream>

using namespace std;

int fail[5003];

int getFail(const string &s, int start) {
    int ans = 0;

    for(int i=0; i <5003; i++){
        fail[i] = 0;
    }

    int j = 0;
    for (int i = 1; i < s.length(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = fail[j - 1];
        }

        if (s[i] == s[j]) {
            fail[i] = ++j;
            ans = max(ans, j);
        }
    }
    
    return ans;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    int ans = 0;

    for (int i = 0; i < s.length(); i++) {
        ans = max(ans, getFail(s.substr(i,s.length()-i), i));
    }
    cout << ans << '\n';

}