본문 바로가기

알고리즘 관련/BOJ

BOJ)13506 카멜레온 부분 문자열

문제: icpc.me/13506


접두사와 접미사가 동시에 될 수 있는 최대 부분 문자열 중 접두사와 접미사가 둘다 아니게도 등장하는 부분 문자열을 카멜레온 부분 문자열이라고 할 때 카멜레온 부분 문자열중에서 가장 길이가 긴 부분 문자열을 출력하는 문제이다.


KMP의 pi배열을 이용한다면 우리는 prefix와 suffix를 동시에 만족시키는 모든 문자열의 길이를 알 수 있다 // pi[l] -> pi[pi[l]] ->pi[pi[pi[l]]] ...


이 때 prefix와 suffix를 둘 다 만족안하게 등장하는 경우는 pi[0]과 pi[length]를 제외하고 현재 확인하는 부분문자열의 길이와 같은 pi[x]가 존재하는 경우이다.


 

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
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> pi;
string a;
void getpi() {
    pi.resize(a.length());
    int j = 0;
    for (int i = 1; i < a.length(); i++) {
        while (j&&a[i] != a[j])
            j = pi[j - 1];
        if (a[i] == a[j])
            pi[i] = ++j;
    }
}
int main() {
    cin >> a;
    getpi();
    int x = pi[a.length() - 1];
    int f = 0;
    while (x) {
        for (int i = 1; i < a.length() - 1; i++)
            if (pi[i] == x) {
                for (int j = 0; j < x; j++)
                    printf("%c", a[j]);
                f = 1;
                break;
            }
        if (f)break;
        x = pi[x - 1];
    }
    if (!f)puts("-1");
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)8892 팰린드롬  (0) 2017.03.13
BOJ)13576 Prefix와 Suffix  (0) 2017.03.13
BOJ)1585 경찰  (0) 2017.03.11
BOJ)4716 풍선  (0) 2017.03.11
BOJ)11407 책 구매하기3  (0) 2017.03.11