[SWEA] 4038. 단어가 등장하는 횟수
[4038. 단어가 등장하는 횟수]
문제
빠른 문자열 비교가 필요하기 때문에 KMP 알고리즘이 필요하다. KMP 알고리즘.
실수
문자열 비교이기 때문에 Rabin-Karp 알고리즘을 사용하였다. 단순하게 pattern 의 hash 값을 구한다음 한칸씩 밀어가면서 hash 값을 비교했다. 하지만 시간 초과로 인해 더 나은 KMP 알고리즘을 찾아 적용시켰다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Solution {
static StringBuilder result = new StringBuilder();
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
long n;
///////////////////////////
String b, s;
int hash, cnt;
///////////////////////////
for (int test_case = 1; test_case <= T; test_case++) {
result.append("#" + test_case + " ");
/////////////////////////////
b = br.readLine();
s = br.readLine();
hash = s.hashCode();
cnt = 0;
for (int i = 0; i <= b.length() - s.length(); i++) {
if (b.substring(i, i + s.length()).hashCode() == hash)
cnt++;
}
result.append(cnt + "\n");
System.out.print(result);
result.setLength(0);
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Solution {
static StringBuilder result = new StringBuilder();
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
///////////////////////////
char[] b, s;
int cnt;
///////////////////////////
for (int test_case = 1; test_case <= T; test_case++) {
result.append("#" + test_case + " ");
/////////////////////////////
b = br.readLine().toCharArray();
s = br.readLine().toCharArray();
cnt = kmp(b, s);
result.append(cnt + "\n");
System.out.print(result);
result.setLength(0);
}
}
static int[] KMP_Table(char[] pattern) {
int[] table = new int[pattern.length];
int j = 0;
for (int i = 1; i < pattern.length; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = table[j - 1];
}
if (pattern[i] == pattern[j]) {
table[i] = ++j;
}
}
return table;
}
static int kmp(char[] str, char[] pattern) {
int[] table = KMP_Table(pattern);
int cnt = 0;
int j = 0;
for (int i = 0; i < str.length; i++) {
while (j > 0 && str[i] != pattern[j]) {
j = table[j - 1];
}
if (str[i] == pattern[j]) {
if (j == pattern.length - 1) {
// i - parttern.length + 1 에서 발견!
cnt++;
j = table[j];
} else {
j++;
}
}
}
return cnt;
}
}
class KMP {
static int[] KMP_Table(char[] pattern) {
int[] table = new int[pattern.length];
int j = 0;
for (int i = 1; i < pattern.length; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = table[j - 1];
}
if (pattern[i] == pattern[j]) {
table[i] = ++j;
}
}
return table;
}
static int kmp(char[] str, char[] pattern) {
int[] table = KMP_Table(pattern);
int cnt = 0;
int j = 0;
for (int i = 0; i < str.length; i++) {
while (j > 0 && str[i] != str[j]) {
j = table[j - 1];
}
if (str[i] == pattern[j]) {
if (j == pattern.length - 1) {
// i - parttern.length + 1 에서 발견!
cnt++;
j = table[j];
} else {
j++;
}
}
}
return cnt;
}
}
댓글남기기