(JAVA) 백준 1305번 : 광고 --- [KMP]

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

1305번: 광고

 

 

이 문제도 문자열 탐색 알고리즘인 KMP 알고리즘을 사용한다.

 

 

 

포인트 몇 가지만 알아보자.

 

 

  1)  광고 문자열은 무한히 반복한다.

 

  2)  무한히 반복하는 문자열 중 일부분만 우리가 확인한다.

 

  3)  그 중, 광고가 될 수 있는 문자열(무한히 반복하는 문자열)이 가능한 경우 중 가장 짧은 문자열의 길이를 구한다.

 

 

그럼, 이를 알기 위에선 어떻게하냐?

 

 

문자열에서 접두사 - 접미사가 같은 문자열의 최대 길이를 구하면 된다.

 

 

접두사와 접미사가 같으면 뭐가되었든 광고 문자열의 같은 시작지점(또는 끝지점) 이란 거니까.

 

 

예를 들어,

 

abaabab 가 있다고 하면

    

       abaabab

pi = 0011232

 

가 되고, pi[n-1] = 2 가 나온다. (전체 문자열의 접두사 / 접미사 같은 문자열 길이를 구해야 하니까.)

 

 

그럼, 광고 문자열의 최소 길이는 전체 길이 - 접미사의 최대 길이 가 되는거고.

*** ab를 제외한 abaab가 최소 길이. 최대는 그럼 abaabab가 되겠지?

*** 만약, bab를 제외한 abaa라고 한다면, abaab 가 나올 수 없다..

*** 마찬가지로 baab도 나올 수 없고..

 

엥? 문제가 끝났다!!!

 

 

 

이상입니다. 감사합니다.

 

 

 

소스코드

---