BAEKJOON 1701번: Cubeditor

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

1701번: Cubeditor

문자열의 최대 길이가 5000이므로 O(N^2)풀이가 가능합니다.

알파벳에서 각 문자가 등장하는 자리를 배열에 저장하고 이를 이용하여 서로 같은 부분의 길이가 얼마나 되는지를 확인하여 주면 됩니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
vector<int>pos[30];
char S[5003];
int main(){
    scanf("%s",S);
    int len=strlen(S),ans=0;
    for(int i=0;i<len;i++){
        int p=S[i]-'a';
        for(int j=0;j<(int)pos[p].size();j++){
            int now=0,l=i;
            for(int k=pos[p][j];k>=0;k--){
                if(pos[p][j]<ans)break;
                if(S[k]==S[l])now++;else break;
                l--;
            }
            ans=max(now,ans);
        }
        pos[S[i]-'a'].push_back(i);
    }
    printf("%d",ans);
    return 0;
}