알고리즘 풀이/백준
[백준][Java] 16916번 부분 문자열 (문자열, KMP)
배게
2021. 9. 21. 04:52
728x90
KMP알고리즘을 이해는 하되, 이 밑에 있는거 통째로 구현할 필요 없음
걍 라인마다 뭔 소리하는지 충분히 이해만 하면 됨
이걸 처음부터 끝까지 구현하는 것은 알고리즘을 잘하는 사람이 아니라 차력쇼를 잘하는거임
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
public class Main {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static List<Integer> li;
static int count;
private static void KMP(String org, String ptn) {
int pi[] = getPi(ptn);
int j=0;
for(int i=0; i<org.length(); i++) {
while(j>0 && org.charAt(i)!=ptn.charAt(j)) {
j = pi[j-1];
}
if(org.charAt(i) == ptn.charAt(j)) {
if(j==ptn.length()-1) {
count = 1;
return;
}
else
j++;
}
}
}
static int[] getPi(String ptn) {
int[] pi = new int[ptn.length()];
int j=0;
for(int i=1; i<ptn.length(); i++) {
while(j>0 && ptn.charAt(i) != ptn.charAt(j)) {
j = pi[j-1];
}
if(ptn.charAt(i) == ptn.charAt(j))
pi[i] = ++j;
}
return pi;
}
public static void main(String[] args) throws IOException{
String origin = br.readLine();
String pattern = br.readLine();
li = new ArrayList<>();
KMP(origin, pattern);
System.out.println(count);
// bw.write("");
// bw.flush();
// bw.close();
}
// private static int stoi(String input) {
// return Integer.parseInt(input);
// }
}
|
cs |