[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;
	}
}