|
| 1 | +package famous_algorithm; |
| 2 | + |
| 3 | +import org.junit.Test; |
| 4 | + |
| 5 | +import static org.hamcrest.CoreMatchers.is; |
| 6 | +import static org.junit.Assert.assertThat; |
| 7 | + |
| 8 | +public class Karp_Rabin_Algorithm { |
| 9 | + |
| 10 | + /* |
| 11 | + TASK |
| 12 | + 장문의 문자열 A가 존재할 때, |
| 13 | + 이 문자열 A 안에 특정 문자열 B가 존재하는지 알 수 있는 방법을 해결한다. |
| 14 | + */ |
| 15 | + |
| 16 | + @Test |
| 17 | + public void test() { |
| 18 | + RabinKarpSearch rbk = new RabinKarpSearch(); |
| 19 | + assertThat(rbk.patternSearch("dgethwabcafg".toCharArray(), "abc".toCharArray()), is(6)); |
| 20 | + } |
| 21 | + |
| 22 | + /* |
| 23 | + SOLVE |
| 24 | + 문자열을 수치로 변환시켜 탐색한다. |
| 25 | + 찾고자 하는 문자열을 hash 값으로 치환하여 |
| 26 | + 본문에서 이와 동일한 hash 값에 대해서만 같은 문자열인지 비교해준다. |
| 27 | + (다른 문자열도 hash 값이 같을 수 있으므로) |
| 28 | + 이 때 핵심은 찾고자 하는 문자열의 hash 값은 물론이고 본문의 hash 값을 효율적으로 구할 수 있는 것이다. |
| 29 | + 즉 찾고자하는 문자열과 비교를 할 때 매번 hash 값을 생성하는 것이 아니고 |
| 30 | + 수학적인 규칙 속에서 이미 계산한 값을 재사용하는 것이 핵심이다. |
| 31 | + */ |
| 32 | + |
| 33 | + public class RabinKarpSearch { |
| 34 | + private int prime = 101; |
| 35 | + |
| 36 | + public int patternSearch(char[] text, char[] pattern) { |
| 37 | + int m = pattern.length; |
| 38 | + int n = text.length; |
| 39 | + long patternHash = createHash(pattern, m - 1); |
| 40 | + long textHash = createHash(text, m - 1); |
| 41 | + |
| 42 | + for (int i = 1; i < n - m + 1; i++) { |
| 43 | + if (patternHash == textHash && checkEqual(text, i - 1, i + m - 2, pattern, 0, m - 1)) { |
| 44 | + return i - 1; |
| 45 | + } |
| 46 | + |
| 47 | + if (i < n - m + 1) { |
| 48 | + textHash = reCalculateHash(text, i - 1, i + m - 1, textHash, m); |
| 49 | + } |
| 50 | + } |
| 51 | + return -1; |
| 52 | + } |
| 53 | + |
| 54 | + private boolean checkEqual(char[] str1, int start1, int end1, char[] str2, int start2, int end2) { |
| 55 | + if (end1 - start1 != end2 - start2) { |
| 56 | + return false; |
| 57 | + } |
| 58 | + while (start1 <= end1 && start2 <= end2) { |
| 59 | + if (str1[start1] != str2[start2]) { |
| 60 | + return false; |
| 61 | + } |
| 62 | + start1++; |
| 63 | + start2++; |
| 64 | + } |
| 65 | + return true; |
| 66 | + } |
| 67 | + |
| 68 | + private long reCalculateHash(char[] str, int oldIndex, int newIndex, long oldHash, int patternLen) { |
| 69 | + long newHash = oldHash - str[oldIndex]; |
| 70 | + newHash = newHash / prime; |
| 71 | + newHash += str[newIndex]*Math.pow(prime, patternLen - 1); |
| 72 | + return newHash; |
| 73 | + } |
| 74 | + |
| 75 | + private long createHash(char[] str, int end) { |
| 76 | + long hash = 0; |
| 77 | + for (int i = 0; i <= end; i++) { |
| 78 | + hash += str[i]*Math.pow(prime, i); |
| 79 | + |
| 80 | + } |
| 81 | + return hash; |
| 82 | + } |
| 83 | + } |
| 84 | + /* |
| 85 | + REFERENCE |
| 86 | + YOUTUBE : https://www.youtube.com/watch?v=H4VrKHVG5qI |
| 87 | + GITHUB : https://github.com/mission-peace/interview/blob/master/src/com/interview/string/RabinKarpSearch.java |
| 88 | + */ |
| 89 | +} |
0 commit comments