[백준] 1305번 : 광고 (KMP 알고리즘) c++ 풀이

접근:

전광판이 무한으로 연결되어서 나오는 형태의 광고이기 때문에 적어도 L 만큼은 광고 할 수 있음이  보장이 되어있다.

문제는 주어진 문자열에 대해서 어떤 광고를 말하는 것인지 최소 길이를 구하는 것이다.

문제의 예에서도 말했듯이, aabaaa 가 주어졌다면, aaba 는 광고가 가능한 최소 길이이다

중요한 것은 반복할 문자열이 그 뒤에 얼마나 겹치는 가이다.

그래서, 최소 길이를 구하려면, 길이 L 에서 최대한 겹치는 부분을 제외한 나머지 부분으로 구해야한다.

위 예로 들자면 aabaaa 처럼 뒤에 2개가, 길이 L이 주어졌을 때, 반복하면 최대로 겹치는 부분이다. 그렇기 때문에 저 2개를 제외한 나머지 부분이 반복해야 할 최소 길이가 된다.

전략:

KMP 알고리즘을 이용하여, 하나씩 길이를 늘려가면서 DP처럼 풀어내는 것이다.

이전 탐색 결과를 이용하여 얼마나 겹치는 지를 확인하면서 가기 때문에 시간 내로 풀기에 적절하다.(O(n + m) 시간 수행)

길이가 주어졌을 때의 최대로 겹치는 수를 구하고,

전체 길이에서 겹치는 수를 빼면, 꼭 포함해야 하는 문자열의 최소 길이가 된다.

 

구현:

#include <iostream>
#include <vector>
using namespace std;

int L;
string str;
vector<int> f;// 길이당 최대 겹치는 부분 조사
int main(){
    cin >> L;
    cin >> str;
    f.resize(L);


    for(int i=1,j=0;i<L;i++){
        while(j>0 && str[i] != str[j]){ //j=0이거나 같은 문자 나올때까지 이동
            j = f[j-1];
        }
        //만약 같은문자면 현재까지 겹치는 수 대입
        if(str[i]==str[j]){
            f[i] = ++j;
        }
        //j==0 이고 str[i] != str[j] 이면 다음줄로 넘어감
    }
    cout << L - f[L-1] << '\n'; //L일때 최대로 겹치는 수 제외한 나머지
    return 0;
}