문자열 패턴 매칭 알고리즘

고지식한 알고리즘 

문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식

시간 복잡도 O(MN)

 

 

라빈-카프 알고리즘

• 문자열 검색을 위해 해시 값 함수를 이용
• 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교
• 최악의 시간 복잡도 O(MN), 평균적으로 선형에 가까운 빠른 속도 ,대략 O(M+N)

 

숫자 문자열 : 6843212431

찾으려는 패턴 : 4321

 

1. 패턴의 해쉬값을 계산 -> 각 자리의 숫자에 자리값을 곱하여 더함 ("4321"은 정수 4321이 됨)
2. 찾고자 하는 문자열에서 4자리씩 해쉬값을 계산 -> (6843, 8432...)
   1. 새로 추가되는 문자와 그전에 읽었던 값을 이용해서 해쉬값을 구함 ((6843 % 1000) * 10 + 2 = 8432)

 

• 처음 해쉬값을 구할때 찾고자 하는 문자열에서 패턴 길이만큼 읽어서 구한다.
• 예제는 패턴의 길이를 4자리 정수로 작게 했지만 패턴이 문자열이며 길이가 커지면 길이를 일정 자리수로 맞추기 위해 mod연산을 취한다.
• 해쉬값이 일치하더라도 실제 패턴이 일치하지 않을 수 있기때문에 해쉬값이 일치하면 문자열 일치를 검사해야 한다.
• ( 15 mod 10 -> 5, 25 mod 10 -> 5, 35 mod 10 -> 5 모두 해쉬값 동일)

 

 

보이어 무어 알고리즘

• 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 같은 문자는 맞춰두고 점프.
• 최악의 시간 복잡도 O(NM), 최선의 시간복잡도 O(N / M), 평균적으로 가장 빠른 속도를 가지는 알고리즘

 

 

문자열 : aaaaabbbbbwater

찾으려는 패턴 : water

 

aaaaabbbbbwater

water   불일치 -> 3칸 점프 (문자열의 a와 패턴의 a를 맞춰 줌)

 

skip 배열

• skip[ch] : 본문 ch 문자에서 패턴 불일치가 발생했을때 본문포인터의 skip횟수
• 패턴에 포함되지 않은 문자들은 본문포인터가 패턴 길이만큼 skip 해야하므로 패턴의 길이가 skip 배열의 값이 됨.
• 패턴 문자들의 skip 배열값 (패턴 마지막 문자는 제외)
  • (패턴문자열의 길이-1) - 각 패턴 문자의 인덱스
• rithm 패턴 문자열의 skip 배열

rithm

문자열에서 r을 만나면 4칸 skip

문자열에서 i를 만나면 3칸 skip

문자열에서 t를 만나면 2칸 skip

문자열에서 h를 만나면 1칸 skip

 

문자열 : a parttern matching algorithm

패턴 : rithm 

1. a parttern matching algorithm -> 2칸 skip
2. a parttern matching algorithm -> 5칸 skip
3. a parttern matching algorithm -> 5칸 skip
4. a parttern matching algorithm -> 5칸 skip
5. a parttern matching algorithm -> 5칸 skip
6. a parttern matching algorithm -> 5칸 skip
7. a parttern matching algorithm -> 일치

 

KMP 알고리즘

• 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
• 패턴을 전처리하여 부분일치 테이블 배열 pi[k]을 구해서 잘못된 시작을 최소화함
• pi[k] : 처음부터 k인덱스까지를 끝으로 하는 부분 문자열에서 일치하는 접두사와 접미사가 일치하는 최대 길이
• 시간 복잡도는 O(M+N)

 

• 파란 부분 동일 -> 4칸 skip

 

pi 배열 생성

• 패턴을 이용하여 부분 일치 테이블 배열 작성
• 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산
• 패턴의 0번째 인덱스를 제외한 각 인덱스마다 맨 앞부터 해당 인덱스까지의 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이로 구함

예) ababaca

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

// KMP 알고리즘(Knuth–Morris–Pratt Algorithm) 
// O(N+M)
public class String_KMPTest {
   public static void main(String[] args) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] text = in.readLine().toCharArray();
      char[] pattern = in.readLine().toCharArray();
      
      int tLength = text.length, pLength = pattern.length;
      
      // 부분일치테이블 만들기 : KMP의 아이디어를 똑같이 적용, W에서 W를 찾는 듯한 행위를 해서...
      int[] pi = new int[pLength];
       for(int i=1, j=0; i<pLength; i++){// i:접미사 포인터(i=1부터 시작: 우리는 부분일치테이블를 만드는게 목적이므로 첫글자 틀리면 0위치로 가야하므로.), j:접두사 포인터
           while(j > 0 && pattern[i] != pattern[j]) j = pi[j-1]; 
           
           if(pattern[i] == pattern[j]) pi[i] = ++j;
           else pi[i] = 0;
       }
      
      int cnt = 0;
      ArrayList<Integer> list = new ArrayList<Integer>();
      // i : 텍스트 포인터 , j: 패턴 포인터 
      for(int i=0,j=0; i<tLength; ++i) { 
         
         while(j>0 && text[i] != pattern[j]) j = pi[j-1]; 
         
         if(text[i] == pattern[j]) { //두 글자 일치
            if(j == pLength-1) { // j가 패턴의 마지막 인덱스라면 
               cnt++; // 카운트 증가
               list.add((i+1)-pLength);  
               j=pi[j]; 
            }else { 
               j++;
            }
         }
      }
      
      System.out.println(cnt);
      if(cnt>0) {
         System.out.println(list);
      }
   }
}