String Matching

• Reference
• String Mtaching 은 O(n)의 Time Complexity로 진행할 수 있다는 점을 숙지하고 있어야한다.
• 기본적으로는 O(NxM)이다. N번 M 개의 문자열을 비교하기 때문이다.
• KMP, Rabin Karp가 유명하다.

KMP Algorithm

• 이는 미스매칭이된 부분에서 앞에서 이미 매칭되어있는 정보를 가지고 빠르게 다시 매칭하는 방법이다.

aaaaabb

aaab
0120

• 해당 문자가 몇번 매칭되고 있는지를 기록하면된다.
  • 문자가 반복되는 패턴을 기억하는 것을 의미한다.
• a는 2번 index까지 매칭되었다는 뜻이고, b에서 미스매칭이된다.
  • b가 0인 이유는 이전 반복되는 문자가 없는 것을 의미한다.

  abcabd
   000120

  • 위 내용을 보면서 숙지하면된다.
  • abc까지는 반복 패턴이 없고, abca 의 a부터 1인덱스 전까지 반복패턴(a)이 있다는 것이고, abcab의 b부터 2인덱스 전까지 반복패턴(ab)이 있다는 뜻이다.

aaaaabb

aaab
0120

• 아무튼 이전 내용에서 봤을 때, b에서 miss matching이 발생했으므로 miss matching이 발생된 원소의 한칸전의 원소의 반복패턴 정보를 확인한다.
• 여기에서는 a(2) 이므로 인덱스가 2인 부분부터 매칭하면된다는 뜻이다.

aaaaabb

 aaab
  aaab

• 또 미스매칭 되었으므로 한칸 전의 문자의 정보를 봤을 때, 2인덱스 원소와 비교하면서 매칭을 확인하면 된다.

dabcabkabcabd
abcabd
000120
 
 abcabd
 000120
 
       abcabd
 	   000120

• 이해를 위해 하나의 예시를 더 공부했다.

Robin Karp

• 코딩테스트에서 주로 사용하는 쉬운 방법이다.
• 먼저 Substring의 hash 값을 구하고, 해당 Substring 크기의 Window를 Sliding 하면서 hash값을 구한다.
• hash값이 일치하는 부분이 있으면, 해쉬 충돌일 가능성을 배제하기 위해 그 때만 문자열 매칭이 되는지를 확인하면 된다.

substr = aaaab -> hash (16)

aaaaabb
aaaaa -> hash (1) x
 aaaab -> hash (16) o
 
 
aaaab - aaaab (String Matching)