[1305번] 광고

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 실패 함수

KMP 알고리즘의 실패 함수에 대해 알고 있으면 해결할 수 있는 문제이다.

실패 함수의 원리 자체가 접두사와 접미사가 얼마나 중첩되어있냐를 의미하는 것이고, 

그 원리를 이용하여 n - pi[n -1]이라는 방식을 이용하면 해결할 수 있게 된다.

좀더 자세한 내용은 다음과 같다.

---

조금만 생각해 보면 문자열 제곱 문제보다도 더 쉽습니다. 

답이 L보다 작으려면 문자열에 반복 구조가 있어야 하는데, 특히 문자열의 접미사와 접두사가 같은 경우가 생겨야 합니다.

예를 들면 "abcdab"는 "ab"가 양끝에서 반복되므로 "abcd"가 반복된다고 추론할 수 있습니다.

"abcabca"는 "a", "abca"가 양끝에서 반복되는데 정답은 작을수록 좋으므로 

반복되는 문자열은 "abcabc"보다는 "abc"를 취하게 됩니다.

그리고, 만약 fail[L-1]이 문자열 길이 절반보다 크다면? 

즉, "ababa"를 예로 보자면 "aba"가 최대로 반복되므로 fail[L-1] = 3입니다. 

이때는 5-3 = 2가 정답이 되겠습니다.

이걸 보면 그냥 fail[L-1] 값에 달려있다는 걸 알 수 있죠. fail[L-1] = 0이면 답은 L이고, 아니면 답은 L - fail[L-1]이 됩니다.

출처 :: http://kks227.blog.me/220917078260

---

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <iostream> #include <cstdio> #include <string> #include <vector>   using namespace std;   vector<int> getPi(string p) {     int m = (int)p.size();     int j = 0;       vector<int> pi(m, 0);       for (int i = 1; i< m; i++) {         while (j > 0 && p[i] != p[j])             j = pi[j - 1];         if (p[i] == p[j])             pi[i] = ++j;     }     return pi; }   int main() {     int n;     char tmp[1000001];     string p;       scanf("%d", &n);     scanf("%s", tmp);       p = tmp;       vector<int> pi = getPi(p);          cout << n - pi[n - 1] << endl;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus