'알고리즘'에 해당되는 글 2건

  1. 2012.02.09 [알고리즘] 카프-라빈 알고리즘 구현해보기 (2)
  2. 2011.12.05 Shortest Path Algorithm (1)
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



아...뭔가 찝찝하게..구현해 논것 같지만;; 작동은 하니....
저작자 표시 비영리 변경 금지
신고

'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

    비밀댓글입니다

2011.12.05 20:59
[Shortest Path Algorithm]

최단거리 알고리즘

부대에 있을때, 스타크래프트에 관한 유닛의 이동에 관해서 궁금증이 생겼었다.

그러니깐,,, 지형을 보고 유닛이 목표지점까지 최단거리로 이동하는것.

그래서 찾아본게 길찾기 알고리즘! 다양한 길찾기가 있었는데, 제일 많이 보이는게 A*알고리즘이었다.

A*알고리즘은 타일기반의 게임에서 적절할것 같았다. 하지만, 스타가 타일기반 게임이긴해도 타일대로 움직이면 뻣뻣(?) 해 보일것 같아, 대충 알고리즘을 이해하고 넘어가기로 했다.

그러던중, 최단거리란게, 단순히 지형의 꼭지점을 지나가면 된다(? 뭔가 말이 이상한데, 아래 그림을 보고 확인하길..) 는생각을 하게 됬다. 그래서 이걸 만들어 보기로 했다.. 

하지만 먼저 검색을 통해 이미 있는 알고리즘이란걸 확인;;;-_-;;
 

출처 : http://www.cs.uwaterloo.ca/~alubiw/shortest-path-lecture.pdf

그래! 바로 내가 생각한게 이거야! 

이미 있을줄은 예상했지만;; 조금 뭔가 아쉽다고 해야 하나;;;ㅋ

 

저작자 표시 비영리 변경 금지
신고

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

[알고리즘] 카프-라빈 알고리즘 구현해보기  (2) 2012.02.09
Shortest Path Algorithm  (1) 2011.12.05
Voronoi diagram  (1) 2011.12.05
Trackback 0 Comment 1
  1. Favicon of http://estellesiahome.tistory.com BlogIcon 에스텔시아 2011.12.11 00:17 신고 address edit & del reply

    A알고리즘...최적화를 위해서 어떤 꼼수를 써야하는지 고민하는게 일품이지.



티스토리 툴바