String Matching [Navie, DFA, KMP]

String Matching

Navie algorithm

[설명]

텍스트의 시작부터 끝까지 패턴과 일치하는지 확인한다.

[시간복잡도]

$O(MN)$

[코드]

 static void search(String pat, String txt)
    {
        int l1 = pat.length();
        int l2 = txt.length();
        int i = 0, j = l2 - 1;
 
        for (i = 0, j = l2 - 1; j < l1;) {
 
            if (txt.equals(pat.substring(i, j + 1))) {
                System.out.println("Pattern found at index "
                                   + i);
            }
            i++;
            j++;
        }
    }

DFA 알고리즘

[특징]

Navie 알고리즘에서 각 숫자에 대한 표기를 하는 방식이다. 첫 글자가 일치하는 곳이 발견되면 1을 표기하고, 그 이후로 일치할 경우 1씩 더 증가시키면서 표기한다.

DFA 트랜지션 테이블을 사용한다.

int R;
int DFA[R][MAX_SIZE];
int DFA(char pattern[]){
	int patLength = strlen(pattern);
	DFA[pattern[0]][0] = 1; /* 시작지점을 1로 설정 */
	for(int X = 0; j = 1; j < patLength; j++)
	{
		for(int c = 0; c < R; c++) DFA[c][j] = DFA[c][X];
		DFA[pattern[j]][j] = j + 1 /* 글자가 일치하는 경우 +1 */
		X = DFA[pattern[j]][X]; /* update X */				
}

KMP 알고리즘

[핵심]

(1) : 불일치 부분을 제외하고 본문과 일치하는 패턴을 찾는다.

(2) : 이 패턴의 접두부와 접미부에서 경계를 찾는데, 접두부와 접미부가 **“최대”**한 같은 구간을 찾는 것이 핵심이다.

(3) : 찾은 패턴의 접미부의 시작점으로 이동하는 것이 핵심이다.

(4) : 만약 (2)에서 경계를 찾지 못했을 경우에는 처음으로 불일치한 부분까지 패턴을 이동시켜 (1)부터 과정을 반복한다.

[code] - python

pattern = 'ababbab'

#  kmp_table
table = [0 for _ in range(len(pattern))]
i = 0
for j in range(1, len(pattern)):
    while i > 0 and pattern[i] != pattern[j]:
        i = table[i-1]

    if pattern[i] == pattern[j]:
        i += 1
        table[j] = i

print(table)

[설명]

table의 0번째 값은 반드시 0이된다. 한글자 문자열에는 접두사, 접미사가 존재하지 않기 때문이다.

i와 j 포인터를 사용한다.

i : 현재 어디까지 일치했는지 기록해놓은 포인터 [초기에 0으로 초기화]

j : 탐색 위치를 표시하는 포인터 [초기에 1로 초기화]

[i = table[i-1] 를 하는 이유]

pattern[i] ≠ pattern[j] 인 상황에서 table[j-1]이 N이라면 이전 N까지는 같다는 뜻이다.

이때 i의 인덱스는 N이기 때문에 i = table[j-1]이라는 등식이 성립된다.

따라서 table[i-1]를 새로운 i로 하고 i와 j를 계속 비교한다.

import java.util.Scanner;
public class KMP {
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-->0)
        {
            String pt = sc.next();String dc = sc.next();
            int fail[] = new int[pt.length()+1];
            int i = 0, j,ans=0;
            for(j = 1; j < pt.length();j++){
                while(i>0 && pt.charAt(j) != pt.charAt(i)) i = fail[i-1];
                if(pt.charAt(i) == pt.charAt(j)){
                    i++;
                    fail[j] = i;
                }
            }
            for(j=0;j<pt.length();j++) System.out.printf("%d ",fail[j]);
            System.out.println();
            j=0;
            for(i = 0; i < dc.length(); i++)
            {
                while (j>0 && dc.charAt(i) != pt.charAt(j)) {
                    j = fail[j-1];
                }
                if(pt.charAt(j) == dc.charAt(i)){
                    if(j==pt.length()-1){
                        ans++;
                        j=fail[j];
                    }
                    else j++;
                }
            }
            System.out.println(ans);
        }
    }
}