'카프-라빈'에 해당되는 글 1건
- 2012.02.09 [알고리즘] 카프-라빈 알고리즘 구현해보기 (2)
카프-라빈 알고리즘?
카프-라빈 알고리즘은 문자열내에서 특정 문자열을 검색하는데 사용되는 알고리즘 중 하나입니다.
자세한 내용은 링크 참초 -> http://carstart.tistory.com/97
소스코드
카프-라빈 알고리즘은 문자열내에서 특정 문자열을 검색하는데 사용되는 알고리즘 중 하나입니다.
자세한 내용은 링크 참초 -> http://carstart.tistory.com/97
소스코드
import java.util.ArrayList; public class SearchTest { public static void main(String[] args) { String ori = "한글/헬로월드asd123asd한글을 찾아봐ㅋㅋㅋ"; String word = "한글"; int index = Searcher.KR_SearchOnce(ori, word); System.out.println("where? : index " + index); if (index == -1) { System.out.println("not found!"); } else { System.out.println("found! : " + ori.substring(index, index + word.length())); } int[] index2 = Searcher.KR_SearchAll(ori, word); for (int i = 0; i < index2.length; i++) { System.out.println(index2[i]); } } } class Searcher { private final static int Q = 2111; // true == 대소문자 구분 public static int[] KR_SearchAll(String ori, String s, boolean charsCase) { if (charsCase) { return KR_SearchAll(ori, s); } else { return KR_SearchAll(ori.toUpperCase(), s.toUpperCase()); } } public static int[] KR_SearchAll(String ori, String s) { if (KR_SearchOnce(ori, s) == -1) return null; ArrayList<Integer> result = new ArrayList<Integer>(); String mori = ori.concat(""); int index = 0; int in = 0; in = KR_SearchOnce(mori, s); index += in; mori = ori.substring(index + s.length()); result.add(index); lb: while (true) { in = KR_SearchOnce(mori, s); index += in + s.length(); if (in == -1) break lb; mori = ori.substring(index + s.length()); result.add(index); } int[] r = new int[result.size()]; for (int i = 0; i < result.size(); i++) { r[i] = result.get(i); } return r; } public static int KR_SearchOnce(String ori, String s) { long ss = getHash(s); long H = 0; int m = s.length(); if (ori.length() < m) return -1; H = getHash(ori.substring(0, s.length())); if (ss == H) return 0; char c, cc; for (int i = 1; i <= ori.length() - m; i++) { c = ori.charAt(i - 1); cc = ori.charAt(i + m - 1); // H = (long) (2 * (H - c * Math.pow(2, m - 1)) + cc) % Q; H = (long) (2 * (H - c * Math.pow(2, m - 1)) + cc); if (ss == H) { if (s.equals(ori.substring(i, i + m))) { return i; } } } return -1; } public static long getHash(String data) { int l = data.length(); long ldata = 0; char c; for (int i = 0; i < l; i++) { c = data.charAt(l - i - 1); ldata += c * Math.pow(2, i); } // return ldata %= Q; return ldata; } }
실행 결과 :
아...뭔가 찝찝하게..구현해 논것 같지만;; 작동은 하니....
where? : index 0
found! : 한글
0
16
아...뭔가 찝찝하게..구현해 논것 같지만;; 작동은 하니....
'Math/Pahycis/Algorithm' 카테고리의 다른 글
[알고리즘] 카프-라빈 알고리즘 구현해보기 (2) | 2012.02.09 |
---|---|
Shortest Path Algorithm (1) | 2011.12.05 |
Voronoi diagram (1) | 2011.12.05 |