문자열 매칭(string matching) 알고리즘

1. Problem

- 한 문자열(A)에 다른 문자열(B)이 포함되어 있는지 단순 비교, KMP, 라빈-카프 알고리즘 3가지를 이용해 확인해 보자..

 

1) 단순 비교: A의 맨 앞에서부터 B가 있는지 확인한다.

 

2) KMP(Knuth-Morris-Pratt): 접두사(prefix)와 접미사(suffix), pi[]를 이용해 비교 연산량을 줄인 알고리즘

  - pi[i]에는 B의 부분 문자열 B[0]~B[i]에서 길이가 부분 문자열보다 짧은 것 중 접두사와 접미사가 같은 것을 찾은 후 가장 긴 값을 저장한다.

  - pi[3]==1이라면, B[0]~B[3]에서 접두사와 접미사의 공통부분의 길이가 1이라는 것이다.

 

3) 라빈-카프(Rabin-Karp): 문자열을 해시(hash) 기법을 이용해 데이터를 단순하게 바꿔서 비교를 한다. 대부분의 해시 값은 문자열마다 다르게 나타나고, 오버플로우가 발생한다 해도 큰 문제는 없다. 오버플로우가 발생하는 것이 걸린다면, 나머지(mod) 연산을 이용하면 된다.

  - 이 알고리즘에서 사용되는 해시 함수는 각 문자의 아스키코드 값에 2의 제곱수를 곱하여 더하는 형식이다. 예를 들어 “abc"라면 해시 값은 97*2^2 + 98*2^1 + 99*2^0 = 683이다.

  - 앞에서부터 차례대로 비교해 나갈 때, 해시 함수를 계속 이용하지는 않는다. 한 칸 이동한 결과는 해시 값에서 가장 앞에 있는 문자의 값을 뺀 후 2를 곱한 다음 새로 맨 뒤에 생긴 문자의 값을 더하면 된다. 예를 들어 "abc"에서 한 칸 이동해 “bcd"가 됐다면 "bcd"의 해시 값은 2*(683-97*2^2) + 100 = 690이 된다.

 

2. Input

1) String A

2) String B

 

3. Output

1) A에 B가 있다면 true, 없다면 false를 반환

2) A에 B가 있다면, 몇 번째에 B가 있는지 반환

- A의 맨 앞의 인덱스는 0번이고, A[i]~A[j]번에 B가 있다면 i를 반환

- B가 A에 여러 개 있다면, 가장 작은 인덱스를 반환

 

4. Example

1) 단순 비교

// A = "abcdabcabc", B = "abcab"
// A[0]~A[4] = "abcda" != B
// A[1]~A[5] = "bcdab" != B
// A[2]~A[6] = "cdabc" != B
// A[3]~A[7] = "dabca" != B
// A[4]~A[8] = "abcab" == B
// 결과: true, index = 4

 

2) KMP

// A = "abcdabcabc, B = "abcab"
// B를 이용해 pi[]를 생성한다.
i	B[0]~B[i]	접두사		접미사	접두사==접미사 중 가장 긴 것	pi[i]
0	a		-		-			-		0
1	ab		a		b			-		0
2	abc		a,ab		c,bc			-		0
3	abca		a,ab,abc	a,ca,bca		a		1
4	abcab		a,ab,abc,abca	b,ab,cab,bcab		ab		2

A에서의 위치 i = 0, B에서의 위치 index = 0
// A[0] == B[0]이므로 다음을 비교해본다.
i = 1, index = 1
// A[1] == B[1]이므로 다음을 비교해본다.
i = 2, index = 2
// A[2] == B[2]이므로 다음을 비교해본다.
i = 3, index = 3
// A[3] == d != B[3] == a이므로 index에 B[0]~B[2]까지의 정보를 업데이트한다.
// -> “abc”에는 접두사, 접미사가 같은 것이 없다.
i = 4, index = pi[index-1] = 0
// A[4] == B[0]이므로 다음을 비교해본다.
i = 5, index = 1
// A[5] == B[1]이므로 다음을 비교해본다.
i = 6, index = 2
// A[6] == B[2]이므로 다음을 비교해본다.
i = 7, index = 3
// A[7] == B[3]이므로 다음을 비교해본다.
i = 8, index = 4
// A[8] == B[4]이고, B의 최대 인덱스는 4이므로 탐색을 종료한다.
// true, index = 4

 

3) 라빈-카프

// A = "abcdabcabc", B = "abcab"
// 'a' == 97
// B의 해시 값 = 97*2^4 + 98*2^3 + 99*2^2 + 97*2^1 + 98*2^0 = 3024
// A[0]~A[4] = "abcda" -> 해시 값 = 97*2^4 + 98*2^3 + 99*2^2 + 100*2^1 + 97*2^0 = 3029 (X)
// A[1]~A[5] = "bcdab" -> 해시 값 = 2*(3029-97*2^4) + 98 = 3052 (X)
// A[2]~A[6] = "cdabc" -> 해시 값 = 2*(3052-98*2^4) + 99 = 3067 (X)
// A[3]~A[7] = "dabca" -> 해시 값 = 2*(3067-99*2^4) + 97 = 3063 (X)
// A[4]~A[8] = "abcab" -> 해시 값 = 2*(3063-100*2^4) + 98 = 3024 (O)
// 결과: true, index = 4

 

5. Code

1) 단순 비교

// main()
String A = "abcdabcabc", B = "abcab";
findbasic1(A, B);
findbasic2(A, B);

static void findbasic1(String A, String B) { // 단순 비교 이용
    int index = -1;
    for(int i=0 ; i<=A.length()-B.length(); i++) { // 비교 시작
        boolean find = true;
        for(int j=0 ; j<B.length() ; j++) {
            if(A.charAt(i+j)!=B.charAt(j)) {
                find = false; break;
            }
        }        
        if(find) {
            index = i; break;
        }
    } // 비교 끝
    if(index==-1)
        System.out.printf("findbasic2(%s,%s) = false\n",A,B);
    else
        System.out.printf("findbasic2(%s,%s) = true, index = %d\n",A,B,index);
}

static void findbasic2(String A, String B) { // substring 이용
    int index = -1;
    for(int i=0 ; i<=A.length()-B.length(); i++) { // 비교 시작
        if(A.substring(i,i+B.length()).equals(B)) {
            index = i; break;
        }
    } // 비교 끝
    if(index==-1)
        System.out.printf("findbasic1(%s,%s) = false\n",A,B);
    else
        System.out.printf("findbasic1(%s,%s) = true, index = %d\n",A,B,index);
}

// 출력 결과
findbasic1(abcdabcabc,abcab) = true, index = 4
findbasic2(abcdabcabc,abcab) = true, index = 4

- 시간 복잡도는 O(MN)

- N은 A의 길이, M은 B의 길이

- 효율적이지는 않지만 코드 작성이 쉽다.

 

2) KMP

// main()
String A = "abcdabcabc", B = "abcab";
findKMP(A, B);

static void findKMP(String A, String B) {
    int a = A.length(), b = B.length();
    int[] pi = new int[b];

    // pi[i]에 접두사==접미사인 문자열의 최대 길이 저장
    int index = 0;
    for(int i=1 ; i<b; i++) {
        while(index>0 && B.charAt(i)!=B.charAt(index))
            index = pi[index-1];
        if(B.charAt(i)==B.charAt(index))
        pi[i] = ++index;
    }

    index = 0; // B에서 문자열 비교하는 위치
    for(int i=0 ; i<a ; i++) {
        while(index>0 && A.charAt(i)!=B.charAt(index)) // 일치하지 않으면
            index = pi[index-1]; // 이전까지는 일치했다는 정보를 저장

        // 모든 글자가 맞을 경우
        if(A.charAt(i)==B.charAt(index)) {
            if(index==b-1) {
                System.out.printf("findKMP(%s, %s) = true, index = %d\n",A,B,index);
                // 첫 매칭만 출력할 경우 이 부분에 return;을 쓰고 끝낸다.
                index = pi[index]; // 모든 답을 찾을 때는 이 부분을 살린다.
            } else
                index++;
        }
    }
}

// 출력 결과
findKMP(abcdabcabc, abcab) = true, index = 4

- 시간 복잡도는 O(M+N)

- N은 A의 길이, M은 B의 길이

- 단순 비교에 비해 훨씬 빠르다.

 

3) 라빈-카프

// main()
String A = "abcdabcabc", B = "abcab";

static void findRK(String A, String B) {
    int hashA = 0, hashB = 0, a = A.length(), b = B.length(), index = 0;
    for(int i=0 ; i<b ; i++) { // B와 A 앞부분의 해시 값 계산
        hashB += B.charAt(i)*(int)Math.pow(2, b-1-i);
        hashA += A.charAt(i)*(int)Math.pow(2, b-1-i);
    }
    
    for(int i=1 ; i<=a-b && hashA!=hashB ; i++) { // A에서의 해시 값 계산
        hashA -= A.charAt(i-1)*(int)Math.pow(2, b-1);
        hashA *= 2;
        hashA += A.charAt(i+b-1);
        if(hashA==hashB)
            index = i;
    }
    
    if(hashA!=hashB)
        System.out.printf("findRK(%s,%s) = false\n",A,B);
    else
        System.out.printf("findRK(%s,%s) = true, index = %d\n",A,B,index);
}

// 출력 결과
findRK(abcdabcabc,abcab) = true, index = 4

- 시간 복잡도는 O(N)

- N은 A의 길이

- 가장 빠른 속도를 자랑한다. 안정성을 더하고자 하면 mod 연산을 추가하면 된다.