백준 BOJ 16900 - 이름 정하기

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

16900번: 이름 정하기

fail 배열이 가지고 있는 값이

접두사와 접미사가 같아지는 최대 길이임을 이용하는 문제.

 

문자열 두개를 최대한 많이 겹쳐내면 전체 문자열의 길이가 가장 짧아지게 되기 때문에

가장 적극적으로 겹쳐내기 위해서 실패함수 값이 담긴 배열을 구해준다

 

가장 적극적으로 겹쳤을 때 전체 문자열의 길이는

(전혀 겹치지 않았을때의 최대 길이) - (겹쳐진 부분만큼의 길이) 이고

 

겹치지 않았을때의 최대 길이는

S.length() * K 로 구할 수 있고,

 

K개의 문자열 연결하면 K-1 번 연결하는 부분이 생기며

겹치는 부분의 길이는 각각 fail[S.length()-1] 번이기 때문에

 

최종적인 정답은

cout << (ll)N*K - (ll)fail[N-1]*(K-1);

 

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int fail[567890];

int main(){
	string S;
	int K;
	
	cin >> S >> K;
	
	int N = S.length();
	
	for(int i=1,j=0; i<N; i++){
		while(j>0 && S[i] != S[j]) j = fail[j-1];
		if(S[i] == S[j]) fail[i] = ++j; 
	}
	
	cout << (ll)N*K - (ll)fail[N-1]*(K-1);
	return 0;
}