[Algorithm] KMP Algorithm 으로 indexOf구현하기

public class indexOf {
    public static void main(String[] args) {
        indexOf s = new indexOf();
        System.out.println(s.indexOf( "abcabfabcabceabcabf", "abcabce"));
    }
    int[] flow ;
    public void setFlow(String str, String target) {
        flow = new int[target.length()+1];
        int i =0 , j = -1;
        flow[0] = -1;
        while(i < target.length()){
            if(j == -1 || str.charAt(i) == target.charAt(j)){
                i++;
                j++;
                flow[i] = j;
            } else j = flow[j];
        }
    }
    public int indexOf(String str, String target){
        this.setFlow(str, target);
        int i = 0, j = 0;
        while(i < str.length()){
            if(j == -1 || str.charAt(i) == target.charAt(j)){
                i++; j++;
            } else j = flow[j];
            if(j == target.length()){
                return i - target.length() + 1;
            }
            
        }
        return -1;
    }
}
 

가장빠르다고 생각되는 문자열 패턴 매칭 알고리즘 중 하나인 KMP알고리즘으로 String.indexOf()를 그대로 구현해보았다.

KMP 알고리즘 자체는 일정한 반복되는 문자열 패턴을 검색하기에 굉장히 효율적인 알고리즘으로써 모든 문자열 탐색에 있어 O(대상문자열.length())만큼의 속도를 나타낸다.

원리는 찾고자하는 문자열의 반복되는 구간을 찾아 링크(연결)를 걸어주는 방식이다. 만약 찾고자하는 문자열이 abcabcd일 때 마지막 d에서 틀렸다고 가정하면 직전abc까지 맞은 것이니 해당 abc와 같은 문자열을 찾아 링크를 걸어준다. 즉 abc전의 abc의 c에 링크를 걸어 이 다음이 a냐고 다시 검사하는 방법인데, 더 상세한 설명은 링크(http://183.106.113.109/30stair/KMP_java/KMP_java.php?pname=KMP_java)를 확인하면 된다.