백준 16900 (이름 정하기) c++

문제

16900번: 이름 정하기

문자열이 s가 주어지면 해당 문자열을 최소 k번 부분문자열로 들어가게 이름을 정하고 이름의 길이를 출력하면

되는 문제입니다.

예를 들어 s = ada 이고 k = 3 일때

이름의 최소길이는 adadada 총 7 입니다.

 

KMP알고리즘의 fail 배열을 이용하여 해결하였습니다.

접두사와 접미사가 같으면 중복으로 처리해서 이름을 최소로 할 수 있기 때문입니다.

위의 예시를 보면 ada가 총 3번 부분문자열로 들어가야합니다.

ada의 fail 배열은 {0, 0, 1} 입니다.

즉 맨 마지막 글자 a만 접두사와 접미사가 같으므로 중복으로 처리가 가능합니다.

마지막에는 겹쳐진 접미사의 길이를 더해주면 됩니다.

k * (문자열의 길이 - fail[맨 마지막 글자]) + fail[맨 마지막 글자]

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll fail[10000001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	string s;
	int k;
	cin >> s >> k;

	for (int i = 1, j = 0; i < s.size(); i++) {
		while (j > 0 && s[i] != s[j])j = fail[j - 1];
		if (s[i] == s[j])fail[i] = ++j;
	}
	if (fail[s.size() - 1])
		cout << k*(s.size()-fail[s.size()-1])+fail[s.size()-1];
	else cout << s.size() * k;



	return 0;
}