[JAVA] Rabin-karp 알고리즘 - 동일 패턴 유무 찾기

가장 쉽게 생각할 수 있는 무지성으로 비교하기

String : ababc

Pattern : abc

 

Step 1. aba != abc

Step 2. bab != abc

Step 3. abc == abc

 

Step 3에서 존재한다고 빠르게 파악할 수 있을 것이다.

각 Step에서 사람처럼 한번에 딱 보면 O(1)의 시간이 걸릴 거 같지만, 사실은 아니다

한 str1과 str2를 비교하기 위해서는 한글자 한글자 비교한다.

 

예를 들어 JAVA의 str1.equals(str2)를 사용한다면(Step 1)

a == a true

b == b true

a != c false

으로 Step 1은 False라고 판단하는 것이다.

다시 말해, 글자 하나하나 보기 때문에 글자가 크거나 하면 시간이 매우 오래 걸린다.

 

이것을 해결할 수 있는 방법 중 하나는 Rabin-karp 알고리즘이다.

 

음 ,, 설명을 하려고 했는데 그림이 필요할 거 같고 그럼 그림을 그려야 하는데 조금 귀찮으니까 코드만 올려야겠다 *^^*

Rabin-karp 알고리즘을 이용하면, eqauls 함수처럼 글자 하나하나를 항상 비교하는 것이 아니라

 맨 앞에 있는 문자(이제 안 볼 문자)에 해당하는 수치 뺴주고, 3 곱해주고(차수가 하나씩 올라가므로),

새롭게 볼 숫자에 해당하는 수치 더해주는 수치적인 계산이기 때문에 시간 복잡도가 높지 않다.

 

Rabin-karp : O(N+M)

Broth-force : O(MN)

 

public class rabin_karp {
	
	public static void r_k(String str, String pattern) {
		
		int answer = 0;
		int pat = 0;
		for(int i=0;i<pattern.length();i++) {
			answer += (pattern.charAt(i)*Math.pow(3, pattern.length()-i-1));
		}
		
		for(int i=0;i<str.length()-pattern.length()+1;i++) {
			if(i==0) {
				for(int j=0;j<pattern.length();j++) {
					pat += str.charAt(j)*Math.pow(3, pattern.length()-j-1);
				}
			}
			else {
				pat -= str.charAt(i-1)*Math.pow(3, pattern.length()-1);
				pat = pat * 3;
				pat += str.charAt(i+2)*Math.pow(3, 0);
			}
			if(answer==pat && str.substring(i,i+pattern.length()).equals(pattern)) {
				System.out.println((i+1)+"번째에서 패턴 등장");
				return;
			}
		}
		System.out.println("발견안됨 ");
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		String str = "AABCDDAACE";
		String pattern = "BCD";
		
		r_k(str,pattern);
	}

}