매개변수화 패턴 매칭

소프트웨어 유지보수에서 중요한 문제 중 하나는 대규모 소프트웨어 시스템에서 중복을 찾아내는 것이다. 코드 구간 사이의 완전 일치뿐만 아니라 매개변수화 일치도 찾고자 하는데, 두 코드 구간 사이의 매개변수화 일치란 한 구간의 매개변수 이름(예: 식별자와 상수)을 일대일(전단사) 함수로 다른 구간의 매개변수 이름으로 바꾸어 한 구간을 다른 구간으로 변환할 수 있다는 뜻이다.

두 알파벳 Σ와 Π가 있다. Σ는 대문자 영어 알파벳이고 Π는 소문자 영어 알파벳이다. Σ의 각 기호는 토큰을 나타내고 Π의 각 기호는 매개변수를 나타낸다.

문자열은 Σ와 Π의 토큰과 매개변수를 임의로 조합하여 구성할 수 있다. 두 문자열 A와 B가 p-일치한다는 것은 다음을 모두 만족한다는 뜻이다.

1. A와 B의 길이가 같다(보다 형식적으로: length(A) = length(B)).
2. A의 각 토큰은 B의 토큰과 대응하고, A의 각 매개변수는 B의 매개변수와 대응한다(보다 형식적으로: 모든 1 ≤ i ≤ length(A)에 대해 (Ai가 토큰이고 Bi가 토큰)이거나 (Ai가 매개변수이고 Bi가 매개변수)).
3. A와 B의 토큰 배열이 완전히 일치한다(보다 형식적으로: 모든 1 ≤ i ≤ length(A)에 대해 Ai가 토큰이면 Ai = Bi).
4. A와 B의 매개변수 배열이 A의 매개변수 이름과 B의 매개변수 이름 사이의 일대일 대응을 정의한다(보다 형식적으로: 모든 1 ≤ i ≤ length(A)에 대해 Ai가 매개변수이면 f(Ai) = Bi인 일대일(전단사) 함수 f: Π → Π가 존재한다).

토큰은 프로그램에서 바꿀 수 없는 부분을 나타내고, 매개변수는 프로그램의 변수를 나타내며, 변수의 모든 출현을 일관되게 바꾸는 한 이름을 바꿀 수 있다. 따라서 A와 B가 p-일치하면 A의 변수 이름을 B의 대응하는 변수 이름으로 바꾸어 두 프로그램을 동일하게 만들 수 있다. 이 두 부분이 더 큰 프로그램의 일부라면 둘 다 하나의 서브루틴 호출로 대체할 수 있다.

Σ와 Π 위의 문자열인 텍스트 T와 패턴 P가 주어진다. T의 부분 문자열 중 P와 p-일치하는 것을 모두 찾아라.

첫 번째 줄에 문자열 P가 주어지고, 두 번째 줄에 문자열 T가 주어진다.

첫 번째 줄에 T의 부분 문자열 중 P와 p-일치하는 것의 개수를 출력한다. 두 번째 줄에 그 부분 문자열들의 오프셋을 공백으로 구분하여 출력한다(관례상 T의 접두사는 오프셋 1을 가진다).

• 1 ≤ length(T) ≤ 1,000,000
• 1 ≤ length(P) ≤ 10,000

패턴 XYabCaCXZddbW는 오프셋 2의 텍스트 부분 문자열 XYdxCdCXZccxW와 p-일치하지만, 오프셋 1의 텍스트 부분 문자열 xXYdxCdCXZccx와는 p-일치하지 않는다.

p-일치가 일어날 때 다음 일대일(전단사) 함수 f가 사용됨을 확인할 수 있다.

• f(a) = d
• f(b) = x
• f(d) = c