접두사, 접미사를 이용한, KMP 문자열 매칭 알고리즘 2 with Java

 

 

---

KMP 문자열 매칭 알고리즘

 

1. 접두사, 접미사 일치 테이블 만들기

그렇다면, KMP 알고리즘의 핵심은 패턴 문자열의 접두사와 접미사 일치 길이를 가지고 있는 일치 테이블을 만드는 것 입니다. 일치 길이를 알고 있어야, 해당하는 만큼 점프하여 문자열 매칭이 이루어지는지 탐색 할 수 있으니까요.

(k : 0부터 시작하는 인덱스)

(i : 1부터 시작하는 인덱스)

1. k와 i의 문자가 같으면 일치 테이블의 값을 일치한 갯수 만큼 증가 시켜 줍니다.

2. k와 i의 문자가 같으면 k와 i의 인덱스를 모두 1씩 증가 시켜줍니다.

3. k와 i의 문자가 다르면 i의 인덱스만 1 증가시켜 주고, k 인덱스는 1 감소하고, 해당 위치의 테이블의 값으로 k인덱스의 위치를 이동 시켜 줍니다. (k 인덱스가 문자가 일치한 만큼의 위치로 이동 하기 위해서)

 

 

이를 java 코드로 표현하면 다음과 같습니다.

int[] makeTable(String pattern) {
    char[] patterns = pattern.toCharArray();
    int[] table = new int[patterns.length];
    int k = 0;
    for (int i = 1; i < patterns.length; i++) {
        while (k > 0 && patterns[i] != patterns[k]) {
            k = table[k - 1];
        }
        if (patterns[i] == patterns[k]) {
            table[i] = ++k;
        }
    }
    return table;
}

 

 

2. KMP 알고리즘 순서도

전체 문자열 : "ababacabacaabacaaba"

패턴 문자열 : "abacaaba"

문자열이 있을때 어떤식으로 탐색 하는지 확인해 보겠습니다.

이것을 java 코드로 나타내면 다음과 같습니다.

public class StringMatching {

    public static void main(String[] args) {
        String parent = "ababacabacaabacaaba";
        String pattern = "abacaaba";
        StringMatching StringMatching = new StringMatching();
        StringMatching.kmp(parent, pattern);
    }

    public void kmp(String parent, String pattern) {
        int[] table = makeTable(pattern);
        char[] parents = parent.toCharArray();
        char[] patterns = pattern.toCharArray();
        int k = 0;
        for (int i = 0; i < parents.length; i++) {
            while (k > 0 && parents[i] != patterns[k]) {
                k = table[k - 1];
            }
            if (parents[i] == patterns[k]) {
                if (k == patterns.length - 1) {
                    System.out.printf("%d번째에서 찾았습니다.\n", i - patterns.length + 2);
                    k = table[k];
                } else {
                    k++;
                }
            }
        }
    }

    private int[] makeTable(String pattern) {
        char[] patterns = pattern.toCharArray();
        int[] table = new int[patterns.length];
        int k = 0;
        for (int i = 1; i < patterns.length; i++) {
            while (k > 0 && patterns[i] != patterns[k]) {
                k = table[k - 1];
            }
            if (patterns[i] == patterns[k]) {
                table[i] = ++k;
            }
        }
        return table;
    }
}