문자열 찾기

워드프로세서의 찾기 기능처럼, 긴 문자열 안에서 원하는 패턴이 나타나는 모든 위치를 찾는 프로그램을 작성하자.

두 문자열 T와 P가 주어진다. P가 T 안에서 몇 번 나타나는지, 그리고 각 등장이 T의 몇 번째 문자에서 시작하는지를 구해야 한다. 이 문제를 문자열 매칭이라고 하며, P를 패턴, T를 텍스트라고 부른다.

T의 길이를 n, P의 길이를 m이라고 하자. 문자는 1번부터 센다고 생각하며, T의 i번째 문자를 T[i], P의 i번째 문자를 P[i]라고 쓴다. 패턴이 텍스트의 i번째 위치에서 나타난다는 것은 T[i]부터 T[i+m-1]까지의 문자가 P[1]부터 P[m]까지와 순서대로 모두 같다는 뜻이다.

다음 그림에서는 T의 1번 위치에서 비교를 시작했지만 7번째 비교에서 두 문자가 달라져 매칭에 실패한다.

      1 2 3 4 5 6 7 8 9 …T : [ A B C D A B C D A B D E ]      | | | | | | XP : [ A B C D A B D ]      1 2 3 4 5 6 7

반면 다음 그림에서는 T의 5번 위치에서 시작한 부분 문자열이 패턴과 모두 일치한다.

      1 2 3 4 5 6 7 8 9 …T : [ A B C D A B C D A B D E ]              | | | | | | |P :         [ A B C D A B D ]              1 2 3 4 5 6 7

모든 시작 위치를 하나씩 확인하는 단순한 방법은 각 위치마다 최대 m번 비교한다. 시작 위치는 최대 n-m+1개이므로 시간 복잡도는 O((n-m+1) × m) = O(nm)이 된다.

더 빠르게 찾으려면 실패한 비교가 알려 주는 정보를 활용해야 한다. 위 그림에서 T[7] != P[7]로 실패했다면, 그 전까지 T[1]부터 T[6]까지는 P[1]부터 P[6]까지와 같았다는 사실도 이미 알고 있다. 패턴 내부의 접두사와 접미사가 겹치는 길이를 이용하면, 이미 확인한 문자를 다시 비교하지 않고 다음 가능한 위치로 이동할 수 있다.

일반화하면, T의 i번 위치에서 시작한 매칭을 검사하다가 T[i+j-1] != P[j]를 발견했다고 하자. 이때 P[1…k] = P[j-k…j-1]를 만족하는 가장 큰 k를 미리 알고 있으면, 다음 비교를 T[i+j-1]와 P[k+1]부터 이어 갈 수 있다. 이 값들을 패턴에 대해 전처리하면 전체 문자열 매칭을 선형 시간에 수행할 수 있다.

이 원리를 이용하여 T와 P가 주어졌을 때 패턴이 나타나는 모든 위치를 출력하시오.

첫째 줄에 텍스트 문자열 T가 주어진다.

둘째 줄에 패턴 문자열 P가 주어진다.

두 문자열의 길이 n, m은 각각 1 이상 1,000,000 이하이다. 문자열은 알파벳 대소문자와 공백으로만 이루어져 있다.

첫째 줄에 T 안에서 P가 나타나는 횟수를 출력한다.

둘째 줄에 P가 나타나는 시작 위치를 오름차순으로 공백으로 구분해 출력한다. 위치는 1번부터 센다. 예를 들어 T의 i번째 문자부터 i+m-1번째 문자까지가 P와 모두 같다면 i를 출력한다.