์๋ํ๋ก์ธ์ ๋ฑ์ ์ฌ์ฉํ๋ ๋์ค์ ์ฐพ๊ธฐ ๊ธฐ๋ฅ์ ์ด์ฉํด ๋ณธ ์ผ์ด ์์ ๊ฒ์ด๋ค. ์ด ๊ธฐ๋ฅ์ ์ฌ๋ฌ๋ถ์ด ์ค์ ๋ก ๊ตฌํํด ๋ณด๋๋ก ํ์.
๋ ๊ฐ์ ๋ฌธ์์ด P์ T์ ๋ํด, ๋ฌธ์์ด P๊ฐ ๋ฌธ์์ด T ์ค๊ฐ์ ๋ช ๋ฒ, ์ด๋ ์์น์์ ๋ํ๋๋์ง ์์๋ด๋ ๋ฌธ์ ๋ฅผ '๋ฌธ์์ด ๋งค์นญ'์ด๋ผ๊ณ ํ๋ค. ์๋ํ๋ก์ธ์์ ์ฐพ๊ธฐ ๊ธฐ๋ฅ์ ์ด ๋ฌธ์์ด ๋งค์นญ ๋ฌธ์ ๋ฅผ ํ์ด์ฃผ๋ ๊ธฐ๋ฅ์ด๋ผ๊ณ ํ ์ ์๋ค. ์ด๋์ P๋ ํจํด์ด๋ผ๊ณ ๋ถ๋ฅด๊ณ T๋ ํ ์คํธ๋ผ๊ณ ๋ถ๋ฅธ๋ค.
ํธ์์ T์ ๊ธธ์ด๋ฅผ n, P์ ๊ธธ์ด๋ฅผ m์ด๋ผ๊ณ ํ์. ์ผ๋ฐ์ ์ผ๋ก, n โฅ m์ด๋ผ๊ณ ๊ฐ์ ํด๋ ๋ฌด๋ฆฌ๊ฐ ์๋ค. n<m์ด๋ฉด ์ด์ฐจํผ P๋ T์ค๊ฐ์ ๋ํ๋ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค. ๋, T์ i๋ฒ์งธ ๋ฌธ์๋ฅผ T[i]๋ผ๊ณ ํํํ๋๋ก ํ์. ๊ทธ๋ฌ๋ฉด ๋ฌผ๋ก , P์ i๋ฒ์งธ ๋ฌธ์๋ P[i]๋ผ๊ณ ํํ๋๋ค.
โย ย 1 2 3 4 5 6 7 8 9 โฆ
T : [ A B C D A B C D A B D E ]
โโย |ย |ย |ย |ย |ย |ย X
P : [ A B C D A B D ]
โย ย ย 1 2 3 4 5 6 7
๋ฌธ์์ด P๊ฐ ๋ฌธ์์ด T ์ค๊ฐ์ ๋ํ๋๋ค๋ ๊ฒ, ์ฆ ๋ฌธ์์ด P๊ฐ ๋ฌธ์์ด T์ ๋งค์นญ์ ์ด๋ฃฌ๋ค๋ ๊ฒ์ด ์ด๋ค ๊ฒ์ธ์ง ์์ ์๋์ ๋ ์๋ฅผ ํตํด ์์๋ณด์. ์์ ์์์ P๋, T์ 1๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ ์คํจํ๋ค. T์ 7๋ฒ ๋ฌธ์ T[7]๊ณผ, P์ 7๋ฒ ๋ฌธ์ P[7]์ด ์๋ก ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ด๋ค.
๊ทธ๋ฌ๋ ์๋์ ์์์ P๋, T์ 5๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ ์ฑ๊ณตํ๋ค. T์ 5๏ฝ11๋ฒ ๋ฌธ์์ P์ 1๏ฝ7๋ฒ ๋ฌธ์๊ฐ ์๋ก ํ๋์ฉ ๋์๋๊ธฐ ๋๋ฌธ์ด๋ค.
โย ย 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
๊ฐ์ฅ ๋จ์ํ ๋ฐฉ๋ฒ์ผ๋ก, ์กด์ฌํ๋ ๋ชจ๋ ๋งค์นญ์ ํ์ธํ๋ค๋ฉด, ์๊ฐ๋ณต์ก๋๊ฐ ์ด๋ป๊ฒ ๋ ๊น? T์ 1๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ด ๊ฐ๋ฅํ์ง ์์๋ณด๊ธฐ ์ํด์, T์ 1๏ฝm๋ฒ ๋ฌธ์์ P์ 1๏ฝm๋ฒ ๋ฌธ์๋ฅผ ๋น๊ตํ๋ค๋ฉด ์ต๋ m๋ฒ์ ์ฐ์ฐ์ด ํ์ํ๋ค. ์ด ๋น๊ต๋ค์ด ๋๋ ํ, T์ 2๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ด ๊ฐ๋ฅํ์ง ์์๋ณด๊ธฐ ์ํด์, T์ 2๏ฝm+1๋ฒ ๋ฌธ์์ P์ 1๏ฝm๋ฒ ๋ฌธ์๋ฅผ ๋น๊ตํ๋ค๋ฉด ๋ค์ ์ต๋ m๋ฒ์ ์ฐ์ฐ์ด ์ํ๋๋ค. ๋งค์นญ์ T์ n-m+1๋ฒ ๋ฌธ์์์๊น์ง ์์ํ ์ ์์ผ๋ฏ๋ก, ์ด๋ฌํ ๋ฐฉ์์ผ๋ก ์งํํ๋ค๋ฉด O( (n-m+1) ร m ) = O(nm) ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ๋ ์๊ณ ๋ฆฌ์ฆ์ด ๋๋ค.
๋ ์ข์ ๋ฐฉ๋ฒ์ ์์๊น? ๋ฌผ๋ก ์๋ค. ์์ ์ ์๋ ์์์, T[7] โ P[7] ์ด๋ฏ๋ก T์ 1๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ด ์คํจ์์ ์๊ฒ ๋ ์๊ฐ์ผ๋ก ๋์๊ฐ์. ์ด๋ ์ฐ๋ฆฌ๋ ๋งค์นญ์ด ์คํจ๋ผ๋ ์ฌ์ค์์, T[7] โ P[7] ๋ผ๋ ์ ๋ณด๋ง์ ์ป์ ๊ฒ์ด ์๋๋ค. ์คํ๋ ค i=1โฆ6์ ๋ํด T[i] = P[i] ๋ผ๊ณ ํ๋ ๊ท์คํ ์ ๋ณด๋ฅผ ์ป์ง ์์๋๊ฐ? ์ด ์ ๋ณด๋ฅผ ์ญ๋ถ ํ์ฉํ๋ฉด, O(n)์ ์๊ฐ๋ณต์ก๋ ๋ด์ ๋ฌธ์์ด ๋งค์นญ ๋ฌธ์ ๋ฅผ ํ์ด๋ด๋ ์๊ณ ๋ฆฌ์ฆ์ ์ค๊ณํ ์ ์๋ค.
P ๋ด๋ถ์ ์กด์ฌํ๋ ๋ฌธ์์ด์ ๋ฐ๋ณต์ ์ฃผ๋ชฉํ์. P์์ 1, 2๋ฒ ๋ฌธ์ A, B๋ 5, 6๋ฒ ๋ฌธ์๋ก ๋ฐ๋ณต๋์ด ๋ํ๋๋ค. ๋, T์ 1๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ด 7๋ฒ ๋ฌธ์์์์ผ ์คํจํ์ผ๋ฏ๋ก T์ 5, 6๋ฒ ๋ฌธ์๋ A, B์ด๋ค.
๋ฐ๋ผ์ T์ 1๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ด ์คํจํ ์ดํ, ๊ทธ ๋ค์์ผ๋ก ๊ฐ๋ฅํ ๋งค์นญ์ T์ 5๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์์ ์ ์ ์๋ค! ๋๋ถ์ด, T์ 5๏ฝ6๋ฒ ๋ฌธ์๋ P์ 1๏ฝ2๋ฒ ๋ฌธ์์ ๋น๊ตํ์ง ์์๋, ์๋ก ๊ฐ๋ค๋ ๊ฒ์ ์ด๋ฏธ ์๊ณ ์๋ค! ๊ทธ๋ฌ๋ฏ๋ก ์ด์ ๋ T์ 7๋ฒ ๋ฌธ์์ P์ 3๋ฒ ๋ฌธ์๋ถํฐ ๋น๊ตํด ๋๊ฐ๋ฉด ๋๋ค.
์ด์ ์ด ๋ฐฉ๋ฒ์ ์ผ๋ฐํ ํด ๋ณด์. T์ i๋ฒ ๋ฌธ์์์ ์์ํ๋ ๋งค์นญ์ ๊ฒ์ฌํ๋ ์ค T[i+j-1] โ P[j]์์ ๋ฐ๊ฒฌํ๋ค๊ณ ํ์. ์ด๋ ๊ฒ P์ j๋ฒ ๋ฌธ์์์ ๋งค์นญ์ด ์คํจํ ๊ฒฝ์ฐ, P[1โฆk] = P[j-kโฆj-1]์ ๋ง์กฑํ๋ ์ต๋์ k(โ j-1)์ ๋ํด T์ i+j-1๋ฒ ๋ฌธ์์ P์ k+1๋ฒ ๋ฌธ์๋ถํฐ ๋น๊ต๋ฅผ ๊ณ์ํด ๋๊ฐ๋ฉด ๋๋ค.
์ด ์ต๋์ k๋ฅผ j์ ๋ํ ํจ์๋ผ๊ณ ์๊ฐํ๊ณ , 1๏ฝm๊น์ง์ ๊ฐ j๊ฐ์ ๋ํด ์ต๋์ k๋ฅผ ๋ฏธ๋ฆฌ ๊ณ์ฐํด ๋์ผ๋ฉด ํธ๋ฆฌํ ๊ฒ์ด๋ค. ์ด๋ฅผ ์ ์ฒ๋ฆฌ ๊ณผ์ ์ด๋ผ๊ณ ๋ถ๋ฅด๋ฉฐ, O(m)์ ์๋ฃํ ์ ์๋ค.
์ด๋ฌํ ์๋ฆฌ๋ฅผ ์ด์ฉํ์ฌ, T์ P๊ฐ ์ฃผ์ด์ก์ ๋, ๋ฌธ์์ด ๋งค์นญ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฌธ์์ด T๊ฐ, ๋์งธ ์ค์ ๋ฌธ์์ด P๊ฐ ์ฃผ์ด์ง๋ค. T์ P์ ๊ธธ์ด n, m์ 1์ด์ 100๋ง ์ดํ์ด๊ณ , ์ํ๋ฒณ ๋์๋ฌธ์์ ๊ณต๋ฐฑ์ผ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์, T ์ค๊ฐ์ P๊ฐ ๋ช ๋ฒ ๋ํ๋๋์ง๋ฅผ ๋ํ๋ด๋ ์์ด ์๋ ์ ์๋ฅผ ์ถ๋ ฅํ๋ค. ๋์งธ ์ค์๋ P๊ฐ ๋ํ๋๋ ์์น๋ฅผ ์ฐจ๋ก๋๋ก ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํด ์ถ๋ ฅํ๋ค. ์์ปจ๋, T์ i๏ฝi+m-1๋ฒ ๋ฌธ์์ P์ 1๏ฝm๋ฒ ๋ฌธ์๊ฐ ์ฐจ๋ก๋ก ์ผ์นํ๋ค๋ฉด, i๋ฅผ ์ถ๋ ฅํ๋ ์์ด๋ค.
๐ก KMP ์๊ณ ๋ฆฌ์ฆ
๐ก ์ ๋์ฌ ์ ๋ฏธ์ฌ ์ค๋ณต๋ถ๋ถ์ ๊ตฌํ๋ pi ๋ฐฐ์ด์ ๊ตฌํ ํ, KMP ์๊ณ ๋ฆฌ์ฆ ์ ์ฉ์ํด
static void getPi() {
int j = 0;
for(int i=1; i<P.length(); i++) {
while(j>0 && P.charAt(i) != P.charAt(j)) {
j = pi[j-1];
}
if(P.charAt(i) == P.charAt(j)) {
pi[i] = ++j;
}
}
}
static void KMP() {
int j = 0;
for(int i=0; i<T.length(); i++) {
while(j>0 && T.charAt(i) != P.charAt(j)) {
j = pi[j-1];
}
if(T.charAt(i) == P.charAt(j)) {
if(j == P.length()-1) {
count++;
ret.add(i-P.length()+2);
j = pi[j];
} else {
j++;
}
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Imple_15 {
static String T, P;
static int[] pi;
static int count = 0;
static ArrayList<Integer> ret = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = br.readLine();
P = br.readLine();
pi = new int[P.length()];
getPi();
KMP();
System.out.println(count);
for(int i : ret) {
System.out.println(i);
}
}
static void getPi() {
int j = 0;
for(int i=1; i<P.length(); i++) {
while(j>0 && P.charAt(i) != P.charAt(j)) {
j = pi[j-1];
}
if(P.charAt(i) == P.charAt(j)) {
pi[i] = ++j;
}
}
}
static void KMP() {
int j = 0;
for(int i=0; i<T.length(); i++) {
while(j>0 && T.charAt(i) != P.charAt(j)) {
j = pi[j-1];
}
if(T.charAt(i) == P.charAt(j)) {
if(j == P.length()-1) {
count++;
ret.add(i-P.length()+2);
j = pi[j];
} else {
j++;
}
}
}
}
}
์ฑ๊ณตโจ