나이브 문자열 매칭 알고리즘 (Naive String match algorithm)

패턴 검색은 컴퓨터 과학에서 중요한 문제이다.
패턴 검색이 필요한 사례들은 매우 많은데 메모장, 파일, 브라우저 또는 데이터베이스에서 문자열을 검색 할 때 패턴 검색 알고리즘으로 검색 결과를 표시하는 것이 그 예이다. 

문제는 매우 긴 문자열에서 내가 찾고자 하는 문자열(패턴)을 어떻게 빠르고 정확하게 찾아낼수 있을까? 이다.

문자열에서 패턴을 검색하기 위해 다양한 알고리즘들이 있는데 그 중 나이브 문자열 매칭 알고리즘 (Naive String match algorithm)은 문자열 처음부터 끝까지 우리가 찾고자 하는 패턴과 일치하는지 하나씩 비교해가면서 단순 무식하게 문자열을 찾는다. 

그림1. Naive String match algorithm

[출처] https://apprize.info/science/algorithms_2/7.html

예를들어 아래 표처럼 문자열 S = "THIS IS A TEST TEXT" 가 있고 찾고자 하는 패턴 P = "TEST" 가 있다고 하자. 

인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
문자열(S)	T	H	I	S		I	S		A		T	E	S	T		T	E	X	T
패턴(P)	T	E	S	T

S[0] 부터 패턴 전체와 일치하는지 확인한다.

 

인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
문자열(S)	T	H	I	S		I	S		A		T	E	S	T		T	E	X	T
패턴(P)	T	E	S	T

S[1] = 'H' 와 P[1] = 'E' 와 일치하지 않기 때문에 S[1] 부터 다시 확인한다.

인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
문자열(S)	T	H	I	S		I	S		A		T	E	S	T		T	E	X	T
패턴(P)		T	E	S	T

이렇게 하나씩 비교할 index 를 증가하면서 순차적으로 찾다보면  S[10] 번배 비교시 패턴과 일치하는 부분을 찾게 되는 것이다.

인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
문자열(S)	T	H	I	S		I	S		A		T	E	S	T		T	E	X	T
패턴(P)											T	E	S	T

 

어려운 부분은 없으니 바로 구현으로 들어간다.

 
public class NaiveAlgorithm {
 
 
    public static void main(String[] args) {
 
        String s = "THIS IS A TEST TEXT";
        String p = "TEST";
 
        // output = 10
        System.out.println(match(s.toCharArray(), p.toCharArray()));
 
    }
 
 
    /*
    * Naive String match algorithm
    * */
    public static int match(char[]s, char[]p) {
 
        int plen = p.length;
        int slen = s.length - plen;
 
        int j, i = 0;
        for(j = 0 ; j < slen ; j++) {
            for(i = 0 ; i < plen ; i++) {
                if(s[j+i] != p[i])
                    break;
            }
 
            if(i == plen) {
                return j;
            }
 
        }
        return -1;
    }
    
}