[Java] 라빈-카프 문자열 탐색 알고리즘

https://coding-food-court.tistory.com/216

위 글에 있는 내용과 그림을 참고하였습니다.

다만, 코드에 오류가 있어서 수정하였습니다.

---

길이가 M인 전체 문자열에서 길이가 N인 문자열을 찾는다고 하면

시간 복잡도 O(M*N)인 알고리즘이다.

이렇게도 풀수는 있지만 시간 복잡도가 상당하다.

 

라빈-카프 문자열 탐색 알고리즘을 사용하면 시간 복잡도가 O(N)으로 감소한다.

 

라빈-카프의 원리

 

찾는 패턴의 길이만큼을 전체 문자열과 찾는 문자열의 해시 코드로 비교한다.

만약 전체 문자열과 찾는 문자열의 해시 코드가 일치한다면 하나씩 비교해가면서 정말로 맞는지 확인한다.

이렇게 한 번더 비교하는 이유는 해시 충돌때문이다.

해시 충돌
A = 0, B = 1, C = 2라고 하고 해시함수가 모두 더하는 해시함수라고 하면
ABC를 해시코드로 변환하면 3이된다.
ACB, BAC.. 등도 마찬가지로 3이된다.
이렇게 해시 충돌이 일어날 수 있기 때문에 한 번더 검사를 하는 것이다.

 

라빈-카프의 해시함수

S = 문자열, S[n]은 문자열 내의 n번째 문자, m은 문자열의 길이를 나타낸다.

 

 

라빈-카프 알고리즘은 한 칸씩 이동하면서 해시 코드를 비교하는데, 한 칸씩 이동할 때마다 해시함수를 구하면 시간 복잡도 O(N*M)인 알고리즘과 다를게 없다.

따라서 기존에 구했던 해시함수를 일부 재활용한다.

처음에 문자열의 해시 코드를 구한 뒤, 이후 한 칸씩 이동할 때는 버리게 되는 문자의 해시코드를 빼주고 새로 얻게되는 문자의 해시코드를 더해주는 방식이다.

위 그림에서 보는 것과 같이 새로운 문자의 해시코드를 계산할 때는 2를 곱해주어 한 칸씩 이동하는 효과를 줄 수가 있다.

 

또한, 해시 값을 구하는 과정에서 문자열이 너무 길어서 자료형의 범위값을 넘어서는 경우는 MOD(모듈러 연산)을 활용한다.

 

Java로 구현

모듈러 연산 X

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main
{	
	static List<Integer> solve(String str, String pattern)
	{
		long strHash = 0, patternHash = 0; //해시 코드를 저장
		int power = 1; //2^0
		int strLen = str.length();
		int patternLen = pattern.length();
		
		List<Integer> idxList = new ArrayList<>();
		
		for(int i = 0; i < strLen - patternLen + 1; ++i) //최소한 찾는 문자열의 길이만큼의 루프를 돌아야 하기 때문에 + 1을 해줌
		{
			if(i == 0) //전체 문자열에 첫 탐색이라면
			{
				for(int j = 0; j < patternLen; ++j) //최초 해시 코드를 설정
				{
					//역순으로 해시 코드 값을 구해나감
					strHash = strHash + str.charAt(patternLen - 1 - j) * power; //전체 문자 해당 구간의 해시코드를 한 문자씩 구해나감
					patternHash = patternHash + pattern.charAt(patternLen - 1 - j) * power; // 찾는 문자의 해시코드를 한 문자씩 구해나감
					if (j < patternLen - 1) power *= 2; //2^0은 기존에 있었으므로, 찾는 문자의 길이 -1까지만
				}
			}
			else strHash = 2 * (strHash - (str.charAt(i - 1) * power)) + str.charAt(patternLen - 1 + i); //기존 해시코드에서 맨 앞 문자의 해시코드는 버리고, 추가되는 문자의 해시코드는 더한다.
			
			if(strHash == patternHash) //해당 구간에서 해시코드가 서로 일치한다면
			{
				boolean flag = true;
				for(int j = 0; j < patternLen; ++j) //한 문자씩 비교함
				{
					if(str.charAt(i + j) != pattern.charAt(j))
					{
						flag = false;
						break;
					}
				}
				if(flag) idxList.add(i); //모든 문자가 일치한다면 idxList에 찾는 문자열의 시작 인덱스를 추가
			}
		}
		return idxList;
	}
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String pattern = br.readLine();
        List<Integer> idxlist = solve(str, pattern);
        for(Integer value : idxlist) System.out.printf("찾는 문자열의 시작위치 : idx[%d]\n", value);
	}
}

 

모듈러 연산 O

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main
{	
	static List<Integer> solve(String str, String pattern)
	{
		final int MOD = 100000007; //모듈러 연산을 위해
		long strHash = 0, patternHash = 0; //해시 코드를 저장
		int power = 1; //2^0
		int strLen = str.length();
		int patternLen = pattern.length();
		
		List<Integer> idxList = new ArrayList<>();
		
		for(int i = 0; i < strLen - patternLen + 1; ++i) //최소한 찾는 문자열의 길이만큼의 루프를 돌아야 하기 때문에 + 1을 해줌
		{
			if(i == 0) //전체 문자열에 첫 탐색이라면
			{
				for(int j = 0; j < patternLen; ++j) //최초 해시 코드를 설정
				{
					//역순으로 해시 코드 값을 구해나감
					strHash = (strHash + str.charAt(patternLen - 1 - j) * power) % MOD; //전체 문자 해당 구간의 해시코드를 한 문자씩 구해나감
					patternHash = (patternHash + pattern.charAt(patternLen - 1 - j) * power) % MOD; // 찾는 문자의 해시코드를 한 문자씩 구해나감
					if (j < patternLen - 1) power = (power * 2) % MOD; //2^0은 기존에 있었으므로, 찾는 문자의 길이 -1까지만
				}
			}
			else strHash = (2 * (strHash - (str.charAt(i - 1) * power % MOD)) + str.charAt(patternLen - 1 + i)) % MOD; //기존 해시코드에서 맨 앞 문자의 해시코드는 버리고, 추가되는 문자의 해시코드는 더한다.
			
			if(strHash == patternHash) //해당 구간에서 해시코드가 서로 일치한다면
			{
				boolean flag = true;
				for(int j = 0; j < patternLen; ++j) //한 문자씩 비교함
				{
					if(str.charAt(i + j) != pattern.charAt(j))
					{
						flag = false;
						break;
					}
				}
				if(flag) idxList.add(i); //모든 문자가 일치한다면 idxList에 찾는 문자열의 시작 인덱스를 추가
			}
		}
		return idxList;
	}
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String pattern = br.readLine();
        List<Integer> idxlist = solve(str, pattern);
        for(Integer value : idxlist) System.out.printf("찾는 문자열의 시작위치 : idx[%d]\n", value);
	}
}