티스토리 뷰

알고리즘 관련/BOJ

BOJ)1305 광고

JASON 자손9319 2017. 2. 8. 01:43

문제: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 > && 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)1305 광고  (0) 2017.02.08
BOJ)11479 서로 다른 부분 문자열의 개수2  (0) 2017.02.08
BOJ)9249 최장 공통 부분 문자열  (0) 2017.02.08
BOJ)5582 공통 부분 문자열  (0) 2017.02.08
TAG
댓글
댓글쓰기 폼