1701 Cubeditor

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

어떤 문자열의 모든 부분 문자열은 모든 suffix의 prefix들이다. 이를 이용하여 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 모든 suffix의 pi 배열을 구해서 최대값을 구해주면 된다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    string str;
    cin>>str;
    int len=str.size(),ans=0;
    for(int k=0;k<len-1;k++)
    {
        string s=str.substr(k,len);
        vector<int> pi(len-k);
        pi[0]=0;
        for(int i=1,j=0;i<len-k;i++)
        {
            while(j>0 && s[i]!=s[j]) j=pi[j-1];
            if(s[i]==s[j]) pi[i]=++j;
            else pi[i]=0;
            ans=ans>pi[i]?ans:pi[i];
        }
    }
    cout<<ans<<'\n';
    return 0;
}