알고리즘) 패턴매칭

 

브루트포스 시간복잡도가 왜저렇더라 [  ]

 

 

 

---

 

다음 문자열을 보는게 아니라

지금 문자열을 봐야

<패턴의 다른 j열들 손가락으로 지우기 

 

 

 

순서 

현재의 x 를 이용해서 복사(Copy)를 먼저 하고,

 그다음 현재 문자열을 이용해서 x 갱신(

 

 

 

 

 

보이어-무어

 

뒤에서부터 비교하다가 미스매치(틀린 문자)가 발생했을 때, 패턴을 얼마나 오른쪽으로 훅 건너뛸지(스킵할지)를 결정합니다.

1. 패턴에 아예 없는 문자인 경우:
   • 텍스트의 해당 문자가 패턴에 존재하지 않는다면, 그 문자가 포함된 어떤 위치도 정답이 될 수 없습니다. 따라서 패턴을 그 문자 다음 위치로 통째로 스킵합니다.
2. 패턴에 있는 문자인 경우 (Rightmost 원칙):
   • 텍스트의 미스매치 문자가 패턴 안에 존재한다면, 그 문자끼리 위치를 맞춰줍니다.
   • 이때 패턴 안에 해당 문자가 여러 개 있다면, 가장 오른쪽에 있는(제일 뒤에 있는) 문자에 맞춰야 합니다. 그래야 실수로 중간에 있는 정답을 놓치고 넘어가는 일을 방지할 수 있습니다. (보수적인 스킵)
3. 이동 결과가 오히려 왼쪽으로 가는 경우:
   • 가장 오른쪽 문자에 맞추려다 보니, 현재 위치보다 패턴을 오히려 왼쪽으로 후진시켜야 하는 모순적인 상황이 발생할 수 있습니다. 이 경우에는 스킵 룰을 적용하지 않고, 단순히 현재 위치에서 +1 (한 칸만 전진) 해줍니다.

 

구현 방법 (right 배열):
위 규칙을 위해 패턴 내의 각 문자가 가장 마지막(오른쪽)에 등장하는 인덱스를 미리 right라는 배열에 저장해 둡니다. (초기값은 -1, 패턴을 훑으며 최신 인덱스로 갱신)

 

 

보이어-무어의 한계:
아이디어는 참신하지만, 맨 앞글자만 다르고 뒤의 글자들은 다 똑같은 패턴/텍스트에서는 스킵을 1칸씩밖에 못하게 되어 결국 브루트 포스처럼 **O(N × M)**의 시간이 걸릴 수 있습니다. (이를 보완하는 추가 장치가 있지만,.....

이것만으로는 아무튼 불완전하다 

 

 

 

 

 

 

right 배열은 텍스트(긴 글)에서 패턴(찾을 단어)을 찾다가 "글자가 서로 안 맞을 때(미스매치)", 패턴을 "오른쪽으로 몇 칸 훅 건너뛸지(스킵)" 결정하는 데 쓰입니다.

 

 

상황 1: 패턴에 아예 없는 글자 때문에 틀렸을 때

긴 텍스트 안에서 NEEDLE을 찾고 있습니다. 맨 뒤 글자인 E부터 비교합니다.

• 텍스트: A P P LKZ X Y
• 패턴:ㅤ N E E D LE

앗, 텍스트는 **K**인데 패턴은 **E**네요. 틀렸습니다! (미스매치)
이때 1칸만 옆으로 이동해서 또 찾으려면 너무 느립니다. 그래서 방금 만든 right 배열(칠판)에게 물어봅니다.

👉 "칠판아, 방금 텍스트에서 나온 저 K라는 글자, 우리 패턴(NEEDLE)에 있니?"

칠판(right 배열)을 보니 K 옆에는 -1이 적혀있습니다. (우리 패턴에 아예 없는 글자라는 뜻이죠.)
어차피 K는 우리 패턴에 없으니까, K가 겹치는 곳은 싹 다 정답이 될 수 없습니다.
그러니 째째하게 1칸씩 이동하지 말고, K를 완전히 벗어나도록 패턴을 통째로 훅! 스킵(건너뛰기)해 버립니다. 엄청나게 시간을 아낄 수 있죠!

---

상황 2: 패턴에 있는 글자 때문에 틀렸을 때 (이게 핵심!)

이번엔 텍스트에 D가 있었습니다.

• 텍스트: X Y Z ADZ X Y
• 패턴:ㅤ N E E D LE

맨 뒤 글자를 비교해보니 텍스트는 D, 패턴은 **E**로 또 틀렸습니다.
다시 칠판(right 배열)에게 물어봅니다.

👉 "칠판아, 방금 텍스트에서 나온 저 D라는 글자, 우리 패턴(NEEDLE)에 있니?"

칠판(right 배열)을 보니 D 옆에는 3이 적혀있습니다! (아하, 0,1,2,3... 3번 자리에 D가 있구나!)
그러면 이번엔 통째로 건너뛰면 안 됩니다. 패턴 안에 D가 있으니까, 텍스트의 D와 패턴의 D가 위아래로 딱 맞게 겹치도록 패턴을 스르륵 오른쪽으로 이동시켜 줍니다.

• 텍스트: X Y Z ADZ X Y
• 패턴이동: ㅤㅤㅤN E EDL E

이렇게 위치를 딱 맞춰준 다음, 다시 맨 뒤부터 비교를 시작하는 겁니다.

 

 

 

 

 

패턴을 처음 내려놓는 위치는 무조건 맨 왼쪽(0번 인덱스)부터 나란히 놓습니다.

 

 

 

 

txt: X  Y  O  A  T  O  M  A  T  O
pat: T  O  M  A  T  O

 

중간 o가 아니라, 젤 오른쪽 o로 맞추면 과거로 가버림 

 

 

• 정답: 1칸
• 이유 (후진 금지 규칙):
  계산법대로라면 (틀린 인덱스 2) - (칠판 값 5) = -3이 되어 패턴이 왼쪽으로 3칸 가야 합니다. 하지만 알고리즘은 이미 확인한 텍스트의 앞부분으로 돌아가지 않습니다. 이렇게 '나쁜 문자 규칙'이 오히려 패턴을 뒤로 밀어버리려 할 때, 보이어-무어 알고리즘은 무조건 현재 위치에서 1칸 오른쪽으로 이동시키는 선택을 합니다. 이는 "최소한 1칸은 전진해서 무한 루프를 방지하고 탐색을 이어가자"는 예외 처리 규칙 때문입니다.

 

 

 

 

 

 

 

 

 

4. 라빈-카프 (Rabin-Karp) 알고리즘

라빈-카프는 문자를 하나하나 비교하는 대신, 비교할 문자열을 숫자(해시 값)로 만들어서 해시(Hash) 값끼리 비교하는 알고리즘입니다.

문제 제기

길이가 M인 문자열의 해시 값을 구하려면 결국 M번의 연산(더하기, 곱하기 등)이 필요합니다. 텍스트를 한 칸씩 이동할 때마다 매번 M번의 연산을 해서 해시값을 새로 구한다면, 어차피 문자를 하나씩 비교하는 브루트 포스와 속도 차이가 없지 않을까요?

 

마법의 해결책: 롤링 해시(Rolling Hash)와 나머지 연산(Modulo)

라빈-카프의 핵심은 이전 텍스트 구간의 해시값을 재활용하여, 다음 구간의 해시값을 단 한 번의 연산(O(1))으로 구하는 것입니다.

• 나머지 연산의 특징: 미리 다 더하거나 곱한 뒤 나머지를 구하나, 중간중간 각각 나머지를 구해서 더하고 곱하나 결과가 항상 똑같습니다. 이를 이용해 값이 너무 커지는 것을 방지(오버플로우 방지)하면서 해시를 구합니다.

 

숫자 세 개가 써진 긴 띠가 있다고 해봅시다. [4 1 2] 3 5
현재 창문에 보이는 숫자는 412입니다. 다음 칸으로 밀면 123이 되죠?

이걸 매번 1*100 + 2*10 + 3 이렇게 계산하는 게 아니라,

1. 맨 앞의 4를 빼고 (412 - 400 = 12)
2. 전체에 10을 곱한 뒤 (12 * 10 = 120)
3. 새로 들어온 3을 더합니다. (120 + 3 = 123)

 

결론:
첫 번째 윈도우의 해시값을 구할 때만 M번의 반복문을 돌고, 그다음부터는 위 수식을 이용해 1번의 연산만으로 다음 해시값을 바로바로 구할 수 있습니다. 해시값이 같을 때만 실제 문자가 같은지 한 번 더 확인(해시 충돌 대비)하면 되므로, 전체 시간 복잡도를 이론적으로 **O(N)**으로 대폭 줄일 수 있습니다.

 

 

 

 

30을 빼야 하는데, 음수가 나올지도 모르니까 안전하게 967(997-30)을 더하자

 

((기존 해시값 + 앞자리 * (997 - 30)) * 10 + 새 글자) % 997

뺴기랑 똑같은 원리다 

 

 

 

왜 하필 '90'을 빼나요? (수치적 이유)
508이라는 숫자는 [3, 1, 4, 1, 5] 전체가 힘을 합쳐 만든 점수입니다.
그중에서 맨 앞자리 **'3'**이 이 점수(508)에 기여하고 있는 지분이 얼마인지 계산해 보니 90이었던 거예요
 "이제 3 너는 나갈 거니까, 네가 점수에 보태줬던 90점 다시 내놔!" 하고 뺏어오는 과정이 바로 508 - 90

 

 

 

 

 창문 크기(5자리)를 보고 미리 계산해둡니다.

• 우리는 5자리 숫자를 쓰니까, 맨 앞자리는 10,000의 자리입니다.
• 10,000을 997로 나누면 나머지가 30입니다.
• 그래서 이 문제 내내 **맨 앞자리의 가중치는 무조건 '30'**으로 고정됩니다.

 

 

(기존 값 - 앞자리 가중치) × 10 + 새 글자

 

 

 

6595를 997로 나누면.....

(1000-3)*6

6595-(6000-18)=595 +  18

(더하기가 됨) 

 

• | (OR) : 둘 중 하나. 예) a|bc는 'a' 또는 'bc'
• * (Star) : 0번 이상 반복. (아예 안 나와도 됨) 예) ab*a는 aa, aba, abba 모두 가능.
• . (Dot) : 임의의 문자 1개를 의미.
• [ ] (대괄호) : 괄호 안의 문자 중 하나. 예) [a-e]는 a, b, c, d, e 중 하나.
• + (Plus) : 1번 이상 반복. (최소 1번은 무조건 나와야 함)
• {n, m} : 횟수 지정. 예) {4}는 정확히 4번 반복, {0,9}는 0번부터 9번 사이 반복.