[Java] 백준 1786번 찾기 문제 - KMP 알고리즘

[Java] 백준 1786번 찾기 문제 - KMP 알고리즘

www.acmicpc.net/problem/1786

1786번: 찾기

 

문제 설명

 

 

내 코드

 

 

 

🎨 Key Point 

 

단어 안에 단어가 몇번 ? 어디에? 포함되어있는 가를 묻는 문제이다

예를들어 I have an apple. I have a pen. 이라는 문장안에 have가 몇번 어느 위치에 있는지 알아내는 문제이다.

시간복잡도의 효율성을 생각하지 않는다면 매우 쉽게 풀 수 있으나, 이 문제가 어려운 이유는 O(n)의 시간복잡도로 풀어야 하기 때문이다. 

 

이러한 문자열 안에 문자열을 찾는 알고리즘을 하기 위해선 KMP알고리즘을 알아야 한다.

KMP 알고리즘은 접두사로 접미사에 얼마나 연속적으로 나오는지 O(n)에 가까운 성능으로 int Table 배열을 만드는 것이다. 

 

찾을 문자열을 P , 찾아야하는 대상의 문자열을 T라고 하면 P<T 라는 전제하에 풀어도 된다. P>T라면 0개 발견될 것이기 때문이다. 

 

우선 찾을 문자열의 P에 얼마나 많은 반복 문자열이 나오는지 조사를 하기 위해 우선 KMP알고리즘을 이용하여 Table을 만들어 놓는다.  [코드 11-21번 줄]