'카프-라빈'에 해당되는 글 1건

  1. 2012.02.09 [알고리즘] 카프-라빈 알고리즘 구현해보기 (2)
2012.02.09 18:06
카프-라빈 알고리즘?

  카프-라빈 알고리즘은 문자열내에서 특정 문자열을 검색하는데 사용되는 알고리즘 중 하나입니다.
  자세한 내용은 링크 참초 -> 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



아...뭔가 찝찝하게..구현해 논것 같지만;; 작동은 하니....
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'Math/Pahycis/Algorithm' 카테고리의 다른 글

[알고리즘] 카프-라빈 알고리즘 구현해보기  (2) 2012.02.09
Shortest Path Algorithm  (1) 2011.12.05
Voronoi diagram  (1) 2011.12.05
Trackback 0 Comment 2
  1. 2012.02.10 10:53 address edit & del reply

    비밀댓글입니다

  2. 2012.02.10 10:55 address edit & del reply

    비밀댓글입니다



티스토리 툴바