문제:icpc.me/1305
광고의 길이중 가장 짧은 광고는 조금만 생각해보면 n-pi[n-1]이라는 걸 알 수 있다.
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 | #include <cstdio> #include <algorithm> #include <vector> #include <string> #include <iostream> using namespace std; vector<int> pi; int n; string x; void getpi(){ int j = 0; for (int i = 1; i < n; i++) { while (j > 0 && x[i] != x[j]) j = pi[j - 1]; if (x[i] == x[j]) pi[i] = ++j; } } int main(){ scanf("%d", &n); pi.resize(n + 1); cin >> x; getpi(); printf("%d\n", n - pi[n - 1]); return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)5398 틀렸습니다 (0) | 2017.02.11 |
---|---|
BOJ)10266 시계 사진들 (0) | 2017.02.08 |
BOJ)11479 서로 다른 부분 문자열의 개수2 (0) | 2017.02.08 |
BOJ)9249 최장 공통 부분 문자열 (0) | 2017.02.08 |
BOJ)5582 공통 부분 문자열 (0) | 2017.02.08 |