(1305) 광고

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 2번째

 

 

 

만약 원래 광고의 길이가 전광판 길이의 절반 이상이라면 지금 보이는 글자는 광고+광고의 접두사라고 할 수 있다. 광고의 접두사가 길어질수록 광고의 길이는 짧아지므로 KMP의 실패 함수의 마지막 인덱스 값을 구하는 것과 같다.

만약 광고의 길이가 전광판 길이의 절반보다 작아 광고+광고+...+광고의 접두사 형태라고 해도 광고 길이만큼 밀었을 때 문자가 일치하고 이는 마지막 인덱스에서 접두사와 접미사가 일치하는 최대 길이가 된다.

따라서 전체 문자열에서 접두사와 접미사가 일치하는 최대 길이만큼 제외한 길이가 구하는 답이 되고, 이는 KMP의 실패 함수 코드로 구할 수 있다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int l;
  string p;
  
  cin >> l >> p;
  
  vector<int> fail(l), ans;
  
  for(int i=1,j=0;i<l;i++){
    while(j>0 && p[i]!=p[j])  j= fail[j-1];
    
    if(p[i]==p[j])  fail[i]= ++j;
  }
  
  cout << l-fail[l-1];
  
  return 0;
}