백준 BOJ 1701 - Cubeditor

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

1701번: Cubeditor

KMP를 뇌에 박기위한 연습 3일차

실패함수 배열을 활용하는 문제였다.

접두사와 접미사가 같아지는 최대 길이가 fail[k] 일때,

접두사와 접미사가 같아지면서 두번 이상 나오는 문자열의 조건을 충족하기 때문에,

실패함수 배열에서의 최대값이 문제에서 요구하는 정답이 된다.

 

접미사는 가변적으로 바뀔수 있는 반면 접두사는 문자열의 제일 앞을 항상 포함하고 있기 때문에,

모든 문자열 쌍에 대한 실패함수 배열을 구하기 위해서는

문자열의 앞글자를 하나씩 잘라내야합니다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

int fail[5678] = {0};

int main(){
	string s;
	cin >> s;
	
	int N = s.length();
	
	int ans = -1;
	while(N){
		memset(fail, 0, sizeof(fail));
		
		//cout << "[" << s << "]\n";
		
		for(int i=0,j=1; j<N; j++){
			while(i>0 && s[i] != s[j]) i = fail[i-1];
			if(s[i] == s[j]) fail[j] = ++i;
		}
		
		for(int i=1; i<=N; i++){ ans = max(fail[i], ans); }
		s = s.substr(1);
		N--;
	}
	cout << ans;
	return 0;
}