문자열 매칭 (String matching)

Opening hook: 문자열 찾기는 쉬워 보이지만 시험에서는 index 문제입니다

String matching을 처음 보면 '그냥 text에서 pattern을 찾으면 되는 것 아닌가?'라고 느낍니다. 실제로 문제 자체는 직관적입니다. 긴 배열 T가 있고, 짧은 배열 P가 있습니다. 우리는 P가 T 안에서 어디서 시작하는지 찾습니다. 하지만 AUD 시험에서는 이 단순함 때문에 오히려 실수가 많이 납니다. 답이 첫 번째 위치 하나인지, 모든 위치 list인지, shift가 0-based인지 1-based인지, pattern이 겹쳐서 나타나는지, hash 값이 같을 때 진짜 match라고 말해도 되는지, FSM state가 shift인지 matched prefix length인지가 모두 함정입니다.

이 chapter의 목표는 '알고리즘 이름을 안다'가 아닙니다. 목표는 칠판 앞에서 String-Matching-Problem을 formal하게 정의하고, NaiveStringMatching의 invariant와 runtime을 말하고, Rabin-Karp가 왜 빠른 후보 검사를 하지만 false hit 검증이 필요한지 설명하고, FSMMatching에서 state st의 의미를 한 문장으로 정확히 말하는 것입니다. KMP는 prefix/failure intuition을 이해하되, 현재 확인한 AUD source window에는 전체 failure table derivation이 드러나지 않으므로 course-grounded claim과 general knowledge를 분리합니다.

• 시험 답안의 첫 문장: text T length n, pattern P length m, finite alphabet Sigma over arrays.
• 시험 답안의 두 번째 문장: output은 all valid shifts L.
• 가장 흔한 오답: match 후 pattern 길이 m만큼 점프해서 overlap을 놓침.
• Rabin-Karp 핵심 오답: hash equality를 real match로 확정함.
• FSM 핵심 오답: state st를 current shift로 착각함.

한 문장 요약: String matching은 모든 \(\text{sft} \text{with} 0 \le \text{sft} \le n-m\quad\text{and}\quad \text{forall} j, T[\text{sft}+j]=P[j]\)sft with 0 ≤ sft ≤ n-m and forall j, T[sft+j]=P[j]를 찾는 문제입니다.

선수 개념과 필수 용어 지도(Prerequisites and vocabulary map)

이 단원을 이해하기 위해 필요한 사전 지식은 많지 않지만, 단어를 정확히 써야 합니다. 첫째, array index입니다. T[sft+j]처럼 시작 위치와 pattern 내부 위치가 더해지는 표기를 자연스럽게 읽어야 합니다. 둘째, finite alphabet(Sigma)입니다. Sheet07은 P와 T의 원소가 유한 alphabet Sigma의 Zeichen(character)라고 둡니다. 셋째, loop invariant(Schleifeninvariante)입니다. NaiveStringMatching의 correctness proof는 이미 처리한 shift들에 대해 L이 정확하다는 invariant로 진행됩니다. 넷째, modulo arithmetic입니다. Rabin-Karp는 큰 숫자를 직접 비교하기 어렵기 때문에 prime q로 나눈 나머지를 사용합니다.

용어 map을 머릿속에 그리면 좋습니다. Text T는 검색 대상입니다. Pattern P 또는 Muster는 찾고 싶은 짧은 배열입니다. Shift sft 또는 Verschiebung은 P[0]을 T의 어디 아래에 놓을지 정하는 시작 위치입니다. Valid shift 또는 gueltige Verschiebung은 그 alignment에서 P 전체가 T window와 같은 경우입니다. Occurrence는 실제 등장입니다. Output list L은 모든 occurrence의 시작 shift를 담습니다. Rabin-Karp의 p는 pattern의 numeric/hash value이고, t(sft)는 sft에서 text window의 value입니다. FSMMatching의 delta는 transition function, st는 state이며, 이 state는 지금까지 읽은 text suffix와 pattern prefix의 match 길이입니다.

• Array index: T[sft+j]를 P[j]와 비교합니다.
• Loop invariant: correctness proof에서 initialization, Fortsetzung, termination을 말합니다.
• Modulo arithmetic: a congruent b mod q는 q로 나눈 나머지가 같다는 뜻입니다.
• Prefix/Suffix: prefix는 앞에서 시작하는 부분, suffix는 뒤에서 끝나는 부분입니다.
• FSM/endlicher Automat: 상태와 transition으로 입력을 한 글자씩 읽습니다.

문제의 엄밀한 정의(Formal problem definition)

Sheet07은 String-Matching-Problem을 명확하게 formuliert합니다. 검색할 text는 length n의 array T이고, pattern은 length m의 array P이며 \(m \le n\)m ≤ n입니다. P와 T의 element는 finite alphabet Sigma의 character입니다. 우리가 찾는 것은 모든 natural number sft입니다. 단, 가능한 sft는 아무 자연수나가 아닙니다. P가 T 안에 완전히 들어가려면 P의 마지막 index m-1이 T의 index n-1을 넘지 않아야 하므로 \(\text{sft} + m - 1 \le n - 1,\)sft + m - 1 ≤ n - 1,즉 \(\text{sft} \le n - m\)sft ≤ n - m입니다. 따라서 \(0 \le \text{sft} \le n-m\)0 ≤ sft ≤ n-m입니다.

이제 valid shift 조건을 씁니다. sft가 valid라는 것은 \(T[\text{sft}, ..., \text{sft}+m-1] = P\)T[sft, ..., sft+m-1] = P라는 뜻이고, element-wise로는 모든 \(0 \le j \le m-1\)0 ≤ j ≤ m-1에 대해 \(T[\text{sft}+j] = P[j]\)T[sft+j] = P[j]라는 뜻입니다. 이 quantifier가 중요합니다. 한두 글자만 맞아서는 valid가 아닙니다. 반대로 모든 j가 맞으면 그 shift는 반드시 L에 들어가야 합니다. 또한 occurrence가 여러 개이면 모두 들어가야 합니다. AUD Sheet07 G2(c)의 예시에서는 \(T=[a,a,b,a,a,a,a,a,b], P=[a,a,b]\)T=[a,a,b,a,a,a,a,a,b], P=[a,a,b]일 때 \(L=[0,6]\)L=[0,6]입니다.

정의 문제에서는 'all valid shifts'와 'for all j'를 빠뜨리지 마세요.

NaiveStringMatching: 가장 단순하지만 증명하기 좋은 기준 알고리즘

NaiveStringMatching은 모든 possible shift를 하나씩 검사합니다. Outer loop는 \(\text{sft}=0\)sft=0부터 n-m까지 돕니다. 각 sft에서 inner loop는 \(j=0\)j=0부터 m-1까지 돌며 P[j]와 T[sft+j]를 비교합니다. mismatch가 발견되면 isValid를 false로 두고, 끝까지 mismatch가 없으면 sft를 L에 append합니다. 마지막에 L을 반환합니다. 이 방법은 똑똑하게 건너뛰지 않습니다. 그래서 빠르지는 않지만, 정의를 그대로 구현하므로 correctness proof가 매우 깨끗합니다.

초보자가 여기서 하는 실수는 세 가지입니다. 첫째, shift를 1부터 n까지로 돌립니다. Sheet07의 pseudocode는 0-based이고 0..n-m입니다. 둘째, 한 shift에서 mismatch가 났다고 다음 shift들이 모두 불가능하다고 착각합니다. naive는 각 shift를 독립적으로 검사합니다. 셋째, match를 찾자마자 return합니다. String-Matching-Problem의 output은 모든 valid shifts이므로 끝까지 검사해야 합니다.

• \(\text{Initialize} L=[]\)Initialize L=[]
• \(\text{sft}=0..n-m\)sft=0..n-m각각에서 \(\text{isValid}=\text{true}\)isValid=true로 시작합니다.
• \(j=0..m-1\)j=0..m-1에 대해 P[j]와 T[sft+j]를 비교합니다.
• 불일치가 나오면 invalid로 표시합니다.
• 끝까지 유효하면 sft를 L에 추가합니다.
• 모든 이동량을 처리한 뒤 L을 반환합니다.

Naive는 inefficient하지만 source definition과 거의 같은 구조라 correctness proof의 기준점이 됩니다.

Correctness proof intuition: L은 이미 지나온 shift들에 대해 정확하다

NaiveStringMatching의 correctness는 outer loop invariant로 말합니다. sft번째 outer loop iteration이 시작되기 직전에 L은 모든 \(\text{유효} \text{shifts} t \text{with} t < \text{sft}\)valid shifts t with t < sft를 정확히 포함한다는 invariant입니다. Initialization은 쉽습니다. \(\text{sft}=0\)sft=0전에는 \(t<0\)t<0인 shift가 없으므로 \(L=[]\)L=[]이 맞습니다. Fortsetzung에서는 invariant가 sft 전에는 맞다고 가정합니다. 현재 iteration에서 algorithm은 T[sft..sft+m-1]이 P와 같은지 symbol by symbol로 검사합니다. valid라면 sft를 L에 넣고, valid가 아니라면 넣지 않습니다. 그러면 다음 iteration sft+1 전에는 L이 모든 \(\text{유효} \text{shifts} t < \text{sft}+1\)valid shifts t < sft+1을 담습니다.

Termination에서는 outer loop가 \(\text{sft}=n-m+1\)sft=n-m+1전에 멈춥니다. invariant에 \(\text{sft}=n-m+1\)sft=n-m+1을 대입하면 L은 모든 \(\text{유효} \text{shifts} t < n-m+1\)valid shifts t < n-m+1을 담습니다. 가능한 shift의 최대가 n-m이므로 이것은 가능한 모든 valid shifts입니다. 따라서 L은 정확한 output입니다. 이 proof에서 핵심은 inner loop의 역할도 짧게 설명하는 것입니다. inner loop가 모든 j를 검사하기 때문에 isValid가 true로 남는 것과 window equality가 동치입니다.

구두시험 답안: Initialization은 empty prefix, Fortsetzung은 current sft를 정확히 append하거나 skip, Terminierung은 \(\text{sft}=n-m+1\)sft=n-m+1대입입니다.

Naive runtime: \(O(\text{nm})\)O(nm)를 외우기 전에 loop count를 세기

Sheet07 solution은 runtime을 loop count로 분석합니다. 모든 기본 연산을 constant time으로 보면 outer loop는 n-m+1번 실행됩니다. 각 outer iteration에서 inner loop는 최대 m번 실행됩니다. 그래서 total runtime은 \(O((n-m+1) \cdot m)\)O((n-m+1) * m)입니다. 이것은 흔히 \(O(\text{nm})\)O(nm)으로 완화해서 말할 수 있지만, 시험에서는 가능하면 먼저 정확한 product를 쓰는 것이 좋습니다. 왜냐하면 shift 후보 개수와 pattern 비교 개수를 이해하고 있다는 증거가 되기 때문입니다.

주의할 점은 worst-case와 실제 실행을 구분하는 것입니다. 어떤 shift에서는 첫 글자에서 mismatch가 나서 inner loop가 빨리 끝날 수 있습니다. 그래도 worst-case에서는 많은 shift가 긴 prefix를 공유해서 거의 m개씩 비교할 수 있습니다. 예를 들어 T가 거의 전부 a이고 P도 앞부분이 a로 길게 이어지다가 마지막에서만 다르면, 각 shift에서 많은 비교를 하고 실패합니다. 따라서 'Naive는 항상 정확히 nm번 비교한다'는 말은 틀립니다. 'Worst-case upper bound가 \(O((n-m+1)m)\)O((n-m+1)m)'이라고 말해야 합니다.

MC trap: best/typical early mismatch를 worst-case guarantee로 일반화하지 마세요.

Worked-through overlap: match 후 m칸 점프하면 왜 틀리는가

Overlap은 String matching에서 가장 쉬우면서도 가장 자주 틀리는 함정입니다. \(T=[a,a,a,a,a,a], P=[a,a,a]\)T=[a,a,a,a,a,a], P=[a,a,a]를 보겠습니다. \(n=6, m=3\)n=6, m=3이므로 가능한 shift는 0,1,2,3입니다. \(\text{sft}=0\)sft=0에서는 \(T[0..2]=[a,a,a]\)T[0..2]=[a,a,a]라서 valid입니다. \(\text{sft}=1\)sft=1에서도 \(T[1..3]=[a,a,a]\)T[1..3]=[a,a,a]입니다. \(\text{sft}=2\)sft=2와 \(\text{sft}=3\)sft=3도 마찬가지입니다. 따라서 \(\text{출력} L=[0,1,2,3]\)output L=[0,1,2,3]입니다.

만약 첫 \(\text{match} \text{sft}=0\)match sft=0을 찾은 뒤 \(\text{pattern} \text{length} m=3\)pattern length m=3만큼 jump해서 \(\text{sft}=3\)sft=3으로 간다면 \(\text{sft}=1\)sft=1과 \(\text{sft}=2\)sft=2를 놓칩니다. 이 jump는 non-overlapping occurrence만 찾을 때는 쓸 수 있을지 모르지만, Sheet07의 String-Matching-Problem은 all valid shifts를 요구합니다. 따라서 일반 문제에서는 match 후에도 다음 후보 shift를 조심해야 합니다. KMP나 FSM 같은 빠른 알고리즘도 overlap을 보존하도록 설계되어야 합니다. 빠르게 건너뛰는 것과 valid occurrence를 생략하는 것은 완전히 다른 일입니다.

반례 한 줄: \(T=\text{aaaaaa}, P=\text{aaa}\)T=aaaaaa, P=aaa에서 m칸 jump는 \(\text{sft}=1,2\)sft=1,2를 놓칩니다.

Rabin-Karp motivation: 비교한 정보를 버리지 않기

Sheet07 G3는 NaiveStringMatching이 relatively inefficient한 이유를 설명합니다. 한 shift에서 text에 대해 얻은 정보를 다른 shift 처리에 사용하지 않기 때문입니다. Rabin-Karp는 window를 숫자로 바꾸어 빠르게 비교하는 아이디어를 사용합니다. alphabet Sigma의 크기를 d라고 보고, 각 character를 0..d-1의 digit처럼 identify합니다. Sheet07은 단순화를 위해 \(\text{Sigma}=\{0,...,9\}, d=10\)Sigma={0,...,9}, d=10인 decimal system을 사용합니다.

\(\text{Pattern} P=[2,1,5]\)Pattern P=[2,1,5]라면 \(p=215\)p=215입니다. Text window T[sft..sft+m-1]도 같은 방식으로 t(sft)라는 숫자로 봅니다. 만약 실제 숫자 p와 t(sft)가 다르면 window는 pattern과 다릅니다. 같으면 pattern과 같습니다. 문제는 m이 커지면 p와 t(sft)가 너무 커질 수 있다는 점입니다. 그래서 modulo q를 사용합니다. modulo는 숫자를 작게 유지해 빠른 candidate test를 가능하게 하지만, collision 때문에 equality가 match 확정은 아닙니다.

• Pattern P를 base-d number p로 계산합니다.
• 각 텍스트 구간을 d진수 값 t(sft)로 계산합니다.
• 다음 window는 이전 window에서 왼쪽 digit을 빼고 오른쪽 digit을 넣어 갱신합니다.
• 큰 수 문제는 prime q modulo로 줄입니다.
• Modulo equality는 candidate이며, symbol verification이 필요합니다.

Rabin-Karp preprocessing: Horner schema로 p와 t0 계산

Sheet07 해설은 p를 계산하는 두 표현을 보여줍니다. 직접 쓰면 \(p=P[0]\)p=P[0]·10ᵐ⁻¹+P[1]·10ᵐ⁻²+…+P[m−1]입니다. 하지만 실제 계산에는 호너 방법(Horner-Schema)이 자연스럽습니다. p를 0으로 시작하고, \(i=0\)i=0부터 m−1까지 \(p=10p+P[i]\)p=10p+P[i]로 갱신합니다. 예를 들어 \(P=[2,1,5]\)P=[2,1,5]이면 p=(2·10+1)·\(10+5=215\)10+5=215입니다. 같은 방식으로 \(t_{0}\)t₀도 T[0..m−1]에서 계산합니다.

이 전처리(preprocessing)의 실행 시간은 \(\Theta(m)\)Θ(m)입니다. 반복문이 m번 도므로 상한이 \(\Theta(m)\)Θ(m)이고, p를 알려면 P를 적어도 한 번 읽어야 하므로 하한도 \(\Theta(m)\)Θ(m)입니다. 나머지 연산을 쓰는 버전에서는 각 단계에서 \(p=(10p+P[i]) \bmod q, t_{0}=(10t_{0}+T[i]) \bmod q\)p=(10p+P[i]) mod q, t₀=(10t₀+T[i]) mod q처럼 관리합니다. 시험에서 '전처리는 공짜'라고 생각하면 안 됩니다. 총 실행 시간이나 알고리즘을 비교할 때는 전처리 비용과 검색 비용을 분리해서 말해야 합니다.

Preprocessing \(\Theta(m)\)Θ(m), search phase는 별도로 분석합니다.

Rolling update: 한 칸 옮길 때 전체 window를 다시 숫자로 만들지 않는다

Rabin-Karp의 핵심 계산은 t(sft+1)을 t(sft)에서 상수 시간에 얻는 것입니다. 길이 m의 window를 한 칸 오른쪽으로 옮기면, 가운데 m-1개의 문자는 그대로 남고 자릿수만 한 칸 올라갑니다. 빠지는 것은 T[sft]의 높은 자리 기여 T[sft]·dᵐ⁻¹이고, 새로 들어오는 것은 T[sft+m]입니다. 따라서 \(h=d\)h=dᵐ⁻¹을 미리 계산해 두면 \(t(\text{sft}+1)=d(t(\text{sft})-T[\text{sft}]h)+T[\text{sft}+m]\)t(sft+1)=d(t(sft)-T[sft]h)+T[sft+m]입니다.

Sheet07의 decimal 예시에서는 \(d=10\)d=10이고 \(h=10\)h=10ᵐ⁻¹입니다. modulo version에서는 h=(dᵐ⁻¹ mod q)를 쓰며 update 전체를 mod q로 계산합니다. 중요한 직관은 'window 전체 m개를 다시 읽지 않는다'입니다. Naive처럼 매 shift에서 m개를 모두 비교하지 않고, rolling hash로 대부분의 shift를 빠르게 제외합니다. 그러나 candidate가 나오면 여전히 문자별 verification이 필요합니다. 이 검증 비용이 Rabin-Karp의 worst-case 논의에서 중요할 수 있습니다.

rolling update 설명은 'left contribution removed, remaining digits shifted, right symbol added' 순서로 말하면 안전합니다.

False hit: Rabin-Karp의 hash equality는 증거가 아니라 후보입니다

Rabin-Karp에서 가장 중요한 객관식 함정은 p와 t(sft)의 q에 대한 나머지가 같다는 사실을 일치 확정으로 읽는 것입니다. Sheet07은 명시적으로 말합니다. 두 나머지가 다르면 실제 값도 다르므로 일치하지 않습니다. 하지만 두 나머지가 같다고 해서 실제 값까지 같다고 결론낼 수는 없습니다. 서로 다른 두 숫자가 같은 나머지를 가질 수 있기 때문입니다. 이런 경우를 거짓 일치(unechter Treffer, false hit)라고 합니다.

Sheet07의 표는 \(P=[3,1,4], q=13\)P=[3,1,4], q=13예시를 줍니다. \(\text{sft}=2,9,13\)sft=2,9,13은 실제 구간이 [3,1,4]라서 일치합니다. 반면 \(\text{sft}=6\)sft=6과 \(\text{sft}=10\)sft=10은 나머지가 p와 같아 후보가 되지만, 실제 구간은 P와 다르므로 거짓 일치입니다. 따라서 RabinKarpMatch 의사코드는 나머지가 같을 때 곧바로 추가하지 않고 \(b=\text{true}\)b=true로 둔 뒤 \(j=0..m-1\)j=0..m-1문자별 검사를 합니다. 이 검사가 통과할 때만 L에 추가합니다.

MC 반박: 같은 나머지는 같은 문자열을 보장하지 않습니다.

FSMMatching: automaton은 shift가 아니라 기억 상태를 들고 간다

Sheet07 후반과 Sheet09 H1은 finite automaton(endlicher Automat)을 이용한 String matching을 다룹니다. FSMMatching의 입력은 text T, transition function delta, pattern length m입니다. Automaton construction은 별도이고, Sheet09 H1(c)는 'without automaton construction' runtime을 묻습니다. Search algorithm은 \(\text{st}=0\)st=0에서 시작해 text를 왼쪽부터 오른쪽으로 한 글자씩 읽습니다. 각 index i 또는 sft에서 \(\text{st}=\text{delta}(\text{st},T[i])\)st=delta(st,T[i])로 state를 갱신합니다. 만약 \(\text{st}=m\)st=m이 되면 방금 pattern 하나가 끝났다는 뜻이므로 i-m+1을 L에 append합니다.

state st의 의미가 핵심입니다. st는 현재 shift가 아닙니다. st는 지금까지 읽은 text prefix가 pattern P[0..st-1]로 끝나고, 그보다 더 긴 prefix로 끝나지는 않는다는 정보를 저장합니다. 다르게 말하면 text read so far의 suffix 중 pattern prefix와 일치하는 가장 긴 길이입니다. 예를 들어 \(\text{st}=3\)st=3이면 방금 읽은 text의 끝 3글자가 pattern의 앞 3글자와 같다는 뜻입니다. 다음 문자를 읽으면 delta가 이 정보를 갱신합니다.

Sheet09 답안 핵심 문장: st speichert die Länge des laengsten Suffixes des gelesenen Textes, das Praefix von P ist.

FSM example intuition: \(P=[n,a,n,o]\)P=[n,a,n,o]에서 \(L=[5,11]\)L=[5,11]

Sheet07 solution의 FSM example은 \(\text{alphabet} \text{Sigma}=\{a,g,n,o\}, \text{pattern} P=[n,a,n,o], \text{text} T=[g,a,n,a,n,n,a,n,o,n,a,n,a,n,o,g]\)alphabet Sigma={a,g,n,o}, pattern P=[n,a,n,o], text T=[g,a,n,a,n,n,a,n,o,n,a,n,a,n,o,g]를 사용합니다. Automaton은 state 0부터 4까지 있습니다. state 4는 \(\text{pattern} \text{length} m=4\)pattern length m=4이므로 accepting state입니다. Text를 한 글자씩 읽으며 st를 갱신하면 index 8에서 \(\text{st}=4\)st=4가 되어 \(\text{shift} 8-4+1=5\)shift 8-4+1=5를 append합니다. 이후 계속 읽다가 index 14에서 다시 \(\text{st}=4\)st=4가 되어 shift 11을 append합니다. 그래서 \(L=[5,11]\)L=[5,11]입니다.

이 예시가 좋은 이유는 overlap과 fallback state를 보여주기 때문입니다. 중간에 n,a,n까지 맞았다가 다음 글자가 o가 아니면, automaton은 무조건 state 0으로만 가는 것이 아니라, 방금 읽은 suffix가 pattern prefix와 얼마나 맞는지에 따라 적절한 state로 이동합니다. 이 점이 prefix/suffix memory입니다. 하지만 시험에서 delta table 전체를 새로 만들라는 문제와, 이미 주어진 delta로 matching runtime을 묻는 문제를 구분해야 합니다. Sheet09는 H1(c)(i)에서 construction 제외 runtime을 묻기 때문에 \(O(n)\)O(n)이 source-grounded answer입니다.

Accepting state 도달 index i에서 output은 i-m+1입니다.

KMP intuition: source-grounded claim과 general knowledge를 분리하기

KMP(Knuth-Morris-Pratt)는 prefix/failure function을 이용해 mismatch 후 어디서 비교를 재개할지 정하는 대표적인 linear-time string matching algorithm입니다. 일반 알고리즘 지식으로는 preprocessing \(O(m)\)O(m), search \(O(n)\)O(n), total \(O(n+m)\)O(n+m)이라고 말할 수 있습니다. Prefix/failure function은 pattern의 각 prefix에 대해 proper prefix이면서 suffix인 가장 긴 길이를 저장해, 이미 맞춘 정보를 버리지 않도록 합니다.

하지만 이 Study Hub에서는 course-specific claim을 조심해야 합니다. 현재 확인한 AUD chunks에서 Sheet07은 Naive와 Rabin-Karp, FSMMatching을 자세히 다루고, Sheet09는 FSMMatching exercise를 다시 묻습니다. 전체 KMP failure table derivation은 확인된 source window에 충분히 나타나지 않습니다. 따라서 이 페이지의 KMP 설명은 '일반 지식'으로 표시합니다. 시험 대비에서는 KMP를 말할 때도 source가 요구하는 notation과 algorithm이 무엇인지 먼저 확인해야 합니다. 만약 문제 statement가 FSMMatching을 주면 KMP table을 끌고 오지 말고 delta/st 의미를 답해야 합니다.

• 일반 지식: KMP는 접두사·실패 함수(prefix/failure function)를 사용합니다.
• 일반 지식: 전처리 \(O(m)\)O(m), 탐색 \(O(n)\)O(n)입니다.
• 현재 자료에서 직접 확인되는 내용: Sheet07의 Naive·Rabin-Karp와 Sheet07·09의 FSMMatching입니다.
• Exam discipline: asked algorithm의 state/preprocessing/runtime을 정확히 분리합니다.

Unsupported course-specific detail은 'general algorithm knowledge'라고 분리해 말합니다.

Naive·Rabin-Karp·FSM·KMP 비교

네 방법을 한 줄씩 비교해 봅시다. Naive는 preprocessing이 거의 없고 모든 shift에서 직접 비교합니다. correctness proof가 쉽지만 worst-case \(O((n-m+1)m)\)O((n-m+1)m)입니다. Rabin-Karp는 pattern과 text window를 numeric/hash value로 바꾸고 rolling update로 \(O(1)\)O(1) 후보 검사를 합니다. modulo q를 쓰면 false hit가 가능하므로 candidate verification이 필요합니다. FSMMatching은 pattern에 대한 transition function delta가 준비되어 있으면 text를 한 번 읽으며 state st를 갱신하고, \(\text{st}=m\)st=m에서 output shift를 냅니다. Search runtime은 construction 제외 \(O(n)\)O(n)입니다. KMP는 일반 지식상 prefix/failure table을 preprocessing하여 search를 \(O(n)\)O(n)에 수행합니다.

시험에서는 '빠르다'보다 조건이 중요합니다. Rabin-Karp는 hash equality가 sufficient condition이 아닙니다. FSM은 delta가 이미 주어졌는지, automaton construction을 포함하는지에 따라 말이 달라질 수 있습니다. KMP는 현재 course source가 요구하는지 확인해야 합니다. Naive는 worst-case가 느리지만 모든 algorithm의 정의와 correctness를 이해하는 baseline입니다.

• Naive: 이동량 사이의 기억 없이 직접 검증하며 \(O((n-m+1)m)\)O((n-m+1)m)입니다.
• Rabin-Karp: 굴림 해시로 후보를 고른 뒤 실제 문자를 검증하며 거짓 일치가 가능합니다.
• FSMMatching: 전이 함수 delta가 주어지면 상태 st를 유지하며 \(O(n)\)O(n)에 탐색합니다.
• KMP: 접두사·실패 함수를 쓰는 일반적인 선형 시간 방법이지만 현재 출처에는 전체 표 유도가 없습니다.

수식 너머의 증명 직관(Proof intuition)

문자열 매칭 알고리즘의 핵심은 다음 위치로 이동할 때 필요한 정보를 얼마나 보존하느냐입니다. 단순 매칭(Naive)은 이동 사이의 정보를 보존하지 않지만 각 위치를 끝까지 비교하므로 증명이 단순합니다. 라빈-카프(Rabin–Karp)는 현재 구간을 압축한 숫자 요약인 해시를 보존합니다. 해시가 다르면 안전하게 탈락시킬 수 있지만, 해시가 같을 때는 실제 문자열 비교가 필요합니다. 유한 상태 기계(FSM)는 지금까지 읽은 텍스트의 접미사 중 패턴의 접두사와 일치하여 앞으로도 의미가 있는 정확한 길이를 상태로 보존합니다. 정확성은 전이 함수 δ가 가장 긴 접미사·접두사 일치를 유지한다는 성질에 기대고 있습니다.

이 관점으로 보면 객관식 함정도 쉽게 정리됩니다. 단순 매칭에서 '첫 일치 뒤 반환'은 문제의 출력 불변식을 깨뜨립니다. 라빈-카프에서 '해시가 같으면 바로 추가'하는 것은 거짓 일치(false hit) 때문에 정확성을 깨뜨립니다. FSM에서 '상태는 이동 위치다'라고 하는 것은 상태 불변식을 잘못 이해한 것입니다. KMP에서 '실패 함수는 다음 출현 위치다'라고 말하는 것도 틀립니다. 실패 함수·접두사 정보는 패턴 내부에서 다시 쓸 수 있는 접두사의 길이를 뜻합니다.

알고리즘마다 '무엇을 기억하는가'를 말하면 proof intuition이 선명해집니다.

시험 답안 틀(Exam answer templates)

정의형 문제에서는 이렇게 답합니다. 'Gegeben ist ein Textarray T der Länge n und ein Musterarray P der Länge \(m \le n\)m ≤ n ueber einem endlichen Alphabet Sigma. Gesucht sind alle Verschiebungen sft mit 0 <= sft <= n-m, sodass für alle 0 <= \(j < m\)j < m gilt \(T[\text{sft}+j]=P[j].\)T[sft+j]=P[j].' 그 다음 output list L을 언급합니다.

Naive correctness 문제에서는 invariant를 바로 씁니다. 'Vor der sft-ten Iteration der aeusseren Schleife enthaelt L genau alle gueltigen Verschiebungen \(t < \text{sft}.\)t < sft.' 그런 다음 initialization, Fortsetzung, termination을 각각 한두 문장으로 처리합니다. Runtime은 outer n-m+1, inner m, total \(O((n-m+1)m)\)O((n-m+1)m)입니다.

Rabin-Karp 문제에서는 p, t(sft), \(h=d\)h=dᵐ⁻¹, q를 말합니다. rolling update를 설명하고, modulo equality는 candidate only라고 강조합니다. FSM 문제에서는 st meaning을 먼저 말합니다. 'st is the length of the longest prefix of P that is a suffix of the text read so far.' \(\text{st}=m\)st=m이면 output i-m+1입니다.

• 정의 답안: T, P, n, m, Sigma, sft 범위, 모든 j에 대한 조건을 말합니다.
• Naive 답안: L 불변식, 초기화·유지·종료, \(O((n-m+1)m)\)O((n-m+1)m)을 말합니다.
• Rabin-Karp 답안: 창의 수치값, 굴림 갱신, mod q, 거짓 일치 검증을 말합니다.
• FSM 답안: st의 의미, delta 갱신, 수용 상태 출력, 구성 제외 \(O(n)\)O(n)을 말합니다.

Edge cases: 작아 보이는 조건이 답 전체를 바꿉니다

String matching의 edge case는 대부분 index와 output convention에서 나옵니다. Sheet07은 \(m \le n\)m ≤ n을 전제로 설명하므로, 이 chapter도 그 전제를 유지합니다. 만약 다른 문제에서 \(m > n\)m > n이 주어지면 가능한 shift가 없으므로 \(L=[]\)L=[]가 자연스럽지만, 그것은 문제 statement가 허용할 때만 말해야 합니다. \(m=1\)m=1이면 가능한 shift는 0..n-1이고, valid shift는 \(T[\text{sft}]=P[0]\)T[sft]=P[0]인 모든 위치입니다. 이 경우에도 output은 첫 위치 하나가 아니라 모든 위치입니다. P가 모든 문자와 같은 한 글자라면 L은 그 문자가 나타나는 모든 index입니다.

또 다른 edge case는 repeated characters입니다. T가 aaaaa처럼 반복되고 P가 aaa처럼 반복되면 overlap이 많이 생깁니다. 이런 input은 naive의 worst-case 논의와 overlap trap을 동시에 보여 줍니다. 반대로 P의 첫 글자가 T에 거의 없으면 naive는 대부분 첫 비교에서 멈추므로 실제 비교 횟수가 작습니다. 그러나 runtime answer에서는 worst-case guarantee를 말해야 하므로 \(O((n-m+1)m)\)O((n-m+1)m)을 유지합니다. 마지막으로 index base를 조심해야 합니다. Sheet07 pseudocode와 이 page는 0-based shift를 사용합니다. 만약 답안에서 1-based occurrence position을 쓰고 싶다면 처음에 convention을 바꾸었다고 말하고, 모든 output을 일관되게 변환해야 합니다.

• \(m \le n\)m ≤ n은 Sheet07의 전제입니다.
• \(m=1\)m=1이면 가능한 shift는 0..n-1입니다.
• repeated-character input은 overlap과 worst-case를 동시에 만듭니다.
• 0-based와 1-based를 섞으면 정답 shift가 하나씩 밀립니다.

Edge case를 말할 때는 'under the Sheet07 assumption \(m \le n\)m ≤ n'처럼 전제를 붙이면 안전합니다.

Inner loop reasoning: isValid는 무엇을 증명하는가

Outer loop invariant만 외우면 proof가 약해질 수 있습니다. 그 invariant가 유지되는 이유는 inner loop가 current shift를 정확히 판정하기 때문입니다. sft가 고정되어 있다고 합시다. isValid는 처음 true입니다. inner loop가 \(j=0\)j=0부터 m-1까지 진행하면서 mismatch를 하나라도 발견하면 false가 됩니다. 따라서 loop가 끝난 뒤 isValid가 true라는 것은 모든 j에서 mismatch가 없었다는 뜻입니다. 즉 \(\text{forall} j, T[\text{sft}+j]=P[j]\)forall j, T[sft+j]=P[j]입니다. 반대로 window가 pattern과 같다면 어떤 j에서도 mismatch가 없으므로 isValid는 true로 남습니다. 그래서 isValid after inner loop iff current sft is valid입니다.

이 작은 equivalence가 outer proof의 연결 고리입니다. Fortsetzung에서 '현재 sft를 검사한다'라고만 쓰면 부족합니다. 무엇으로 검사하는지, 왜 정확한지 한 문장을 붙여야 합니다. 예를 들어 'Die innere Schleife vergleicht alle m Positionen; daher ist isValid genau dann true, wenn \(T[\text{sft}..\text{sft}+m-1]=P\)T[sft..sft+m-1]=P gilt'라고 쓰면 좋습니다. 시험 채점자는 이 문장을 보고 append/skip이 arbitrary choice가 아니라 valid condition의 정확한 구현임을 확인할 수 있습니다.

Correctness proof에서 inner loop equivalence 한 문장을 넣으면 답안이 훨씬 단단해집니다.

Rabin-Karp correctness: 빠른 reject와 느린 accept의 비대칭

Rabin-Karp의 정확성을 직관적으로 설명할 때는 두 방향을 분리해야 합니다. 첫째, p와 t(sft)의 q에 대한 나머지가 다르면 실제 값도 다릅니다. 실제 값이 같다면 어떤 q로 나누어도 나머지도 같아야 하기 때문입니다. 따라서 나머지 불일치는 안전한 불일치 증거입니다. 이때는 문자별 검증을 하지 않아도 됩니다. 둘째, 두 나머지가 같으면 실제 값이 같을 수도 있고 다를 수도 있습니다. 서로 다른 숫자가 같은 나머지를 가질 수 있기 때문입니다. 따라서 나머지 일치는 확정 증거가 아니라 후보 증거입니다.

이 비대칭을 이해하면 RabinKarpMatch 의사코드가 자연스럽습니다. 두 나머지가 같을 때 곧바로 추가하지 않고 \(b=\text{true}\)b=true로 둔 뒤 j 반복문으로 실제 P[j]와 T[sft+j]를 비교합니다. 불일치가 있으면 \(b=\text{false}\)b=false가 되고 추가하지 않습니다. b가 끝까지 true로 남을 때만 L에 추가합니다. 즉 Rabin-Karp의 출력 정확성은 해시 검사만으로 성립하지 않고, 해시 검사와 직접 검증을 합쳐야 성립합니다. 해시는 대부분의 유효하지 않은 이동량을 빠르게 버리기 위한 필터입니다. 블룸 필터의 거짓 양성 직관과도 비슷하지만, 여기서는 후보 뒤에 정확한 검증을 수행한다는 점이 중요합니다.

• 나머지가 다르면 실제 값도 같을 수 없습니다.
• 나머지가 같다고 실제 값까지 같은 것은 아닙니다.
• 따라서 해시가 같으면 바로 추가하지 않고 검증합니다.
• 올바른 출력은 후보를 실제 문자로 확인한 뒤에만 얻습니다.

Rabin-Karp를 'probabilistic guess'처럼 말하지 말고, modulo filter plus exact verification으로 말하세요.

Rabin-Karp runtime nuance: 평균을 말하기 전에 worst-case를 조심하기

Rabin-Karp는 굴림 갱신(rolling update) 덕분에 각 이동량의 해시 후보 검사를 \(O(1)\)O(1)에 수행할 수 있습니다. 전처리로 p, t0, h를 계산하는 데 \(\Theta(m)\)Θ(m)이 들고, n-m+1개의 이동량을 순회하며 굴림 갱신을 수행합니다. 하지만 나머지가 같은 경우가 자주 발생하면 각 후보마다 문자별 검증이 필요합니다. 검증 하나는 최악의 경우 \(O(m)\)O(m)입니다. 따라서 'Rabin-Karp는 항상 \(O(n+m)\)O(n+m)'이라고 말하면 위험합니다. 좋은 해시와 q, 보통 입력에서는 후보가 적어 빠르게 동작하지만, 최악의 경우에는 많은 거짓 일치 또는 실제 후보 때문에 검증 비용이 커질 수 있습니다.

현재 Sheet07의 핵심은 정확한 평균 시간 정리보다 작동 원리입니다. p와 t0를 \(\Theta(m)\)Θ(m)에 계산하고, t(sft+1)을 상수 시간에 굴림 갱신하며, 나머지 충돌 때문에 직접 검증한다는 점입니다. 시험에서 실행 시간의 범위가 모호하면 전처리, 굴림 순회, 후보 검증 비용을 분리해서 쓰는 것이 가장 안전합니다. 즉 전처리 \(\Theta(m)\)Θ(m), 이동량마다 갱신 \(O(1)\)O(1), 후보 하나마다 검증 \(O(m)\)O(m)이라고 쓰면 근거 없는 단정 없이 구조를 정확히 전달할 수 있습니다.

Rabin-Karp runtime은 candidate verification을 빼먹지 않는 것이 핵심입니다.

FSM transition intuition: delta는 fallback을 미리 표로 만든 것입니다

FSMMatching에서 delta(st,c)는 현재 matched-prefix length가 st이고 새 character c를 읽었을 때 다음 matched-prefix length를 알려줍니다. 이 transition은 '방금까지 맞았던 정보와 새 문자를 합친 문자열의 suffix 중 pattern prefix와 가장 길게 맞는 것'을 찾는다고 생각하면 됩니다. 예를 들어 pattern이 \(P=[n,a,n,o]\)P=[n,a,n,o]이고 현재 \(\text{st}=3\)st=3이라면 지금까지 text 끝이 [n,a,n]과 맞았다는 뜻입니다. 다음 문자가 o이면 \(\text{st}=4\)st=4가 되어 match가 끝납니다. 다음 문자가 o가 아니라 n이라면 완전히 0으로 떨어질 수도 있고, suffix [n]이 pattern prefix [n]과 맞기 때문에 \(\text{st}=1\)st=1이 될 수도 있습니다. 이런 fallback 정보가 delta에 들어 있습니다.

이 설명은 KMP intuition과 연결되지만, 시험에서는 표현을 조심합니다. FSM problem에서 우리는 delta를 transition function으로 받거나 직접 automaton을 그립니다. KMP problem에서는 failure/prefix table을 사용합니다. 두 방식 모두 prefix/suffix overlap을 재사용한다는 큰 직관은 같지만, 답안에서 요구한 object가 다릅니다. Sheet09가 'endlichen Automaten zeichnen'이라고 하면 states와 labeled transitions를 그려야 하고, 'FSMMatching runtime without automaton construction'이라고 하면 delta가 이미 준비된 search loop의 \(O(n)\)O(n)을 말해야 합니다.

delta는 current alignment 그림이 아니라, reusable suffix/prefix length를 갱신하는 table입니다.

이 장을 능동적으로 공부하는 방법(How to study actively)

이 단원은 눈으로 읽으면 쉬워 보이지만, 손으로 table을 채워야 실력이 생깁니다. 첫 번째 drill은 definition drill입니다. 아무 T와 P를 잡고 n, m, possible shift range, valid shift condition을 말합니다. 두 번째 drill은 naive scan입니다. 작은 T와 P를 만들고 sft별 window, first mismatch 위치, L after row를 표로 적습니다. 세 번째 drill은 proof drill입니다. NaiveStringMatching의 outer invariant를 보지 않고 말하고, initialization, Fortsetzung, termination을 각각 20초 안에 설명합니다.

네 번째 drill은 Rabin-Karp false-hit drill입니다. modulo q가 같아도 실제 window가 다를 수 있음을 숫자 예시로 설명합니다. Sheet07의 \(q=13 \text{table}\)q=13 table을 외우려 하지 말고, 왜 \(\text{sft}=6\)sft=6과 10이 false hit인지 window를 직접 비교합니다. 다섯 번째 drill은 FSM state drill입니다. \(\text{st}=0..m\)st=0..m이 무엇을 뜻하는지 pattern prefix length로 말하고, \(\text{st}=m\)st==m일 때 output이 왜 i-m+1인지 작은 example로 계산합니다. 마지막 drill은 source split입니다. '이 fact는 Sheet07/Sheet09 source-backed인가, 아니면 KMP general knowledge인가?'를 구분합니다. 이 습관이 unsupported course-specific claim을 막아 줍니다.

• 정의 연습: T, P, n, m, Sigma와 sft 범위를 말합니다.
• Naive 표 연습: 각 창, 불일치 위치, 행 처리 뒤의 L을 적습니다.
• 증명 연습: 불변식의 초기화·유지·종료를 말합니다.
• Rabin-Karp 연습: 후보와 거짓 일치를 구분합니다.
• FSM 연습: 상태 의미와 출력 i-m+1을 설명합니다.
• 출처 구분 연습: 강의에서 확인되는 내용과 일반 지식을 나눕니다.

Counterexample bank: MC 문장을 빠르게 반박하는 작은 입력들

Multiple choice에서는 긴 proof보다 작은 반례가 더 빠를 때가 많습니다. 'Occurrence는 겹칠 수 없다'라는 문장은 \(T=\text{aaaaaa}, P=\text{aaa}\)T=aaaaaa, P=aaa하나로 반박됩니다. 'shift range는 0..n-1이다'라는 문장은 \(n=5, m=3\)n=5, m=3일 때 \(\text{sft}=4\)sft=4를 놓아 보면 P[2]가 T[6]을 요구하게 되어 text 밖으로 나간다는 설명으로 반박됩니다. '첫 글자만 맞으면 valid shift다'라는 문장은 \(T=[a,b], P=[a,a]\)T=[a,b], P=[a,a]로 충분합니다. 첫 글자는 맞지만 두 번째에서 mismatch입니다.

Rabin-Karp 문장도 반례 bank를 준비합니다. '같은 modulo value면 같은 string이다'는 일반 정수 반례로도 깨집니다. 예를 들어 \(q=13\)q=13에서 314과 132는 둘 다 나머지 2를 가질 수 있지만 숫자 자체는 다릅니다. Sheet07 table은 이 추상 반례를 실제 string window false hit로 보여 줍니다. FSM 문장에서는 'st is shift'를 반박하려면 st의 범위와 sft의 범위를 비교합니다. st는 0..m 사이를 오가는 state이고, sft 또는 i는 0..n-1까지 증가하는 text index입니다. 같은 종류의 값이 아닙니다.

• No overlap claim 반례: \(T=\text{aaaaaa}, P=\text{aaa}.\)T=aaaaaa, P=aaa.
• Wrong shift range 반례: \(n=5, m=3\)n=5, m=3에서 \(\text{sft}=4\)sft=4는 text 밖을 참조합니다.
• First-character-only claim 반례:\(T=[a\)T=[a\(b]\)b]\(P=[a\)P=[a\(a].\)a].
• Hash-equality claim 반례: same modulo remainder but different windows.
• st-is-shift claim 반례: st in 0..m, text index in 0..n-1.

반례는 작을수록 좋습니다. 단, course source의 notation과 index convention을 유지하세요.

Self-grading rubric: 답안을 채점자 눈으로 점검하기

String matching 답안을 쓰고 나면 네 줄 rubric으로 스스로 채점합니다. 첫째, definition line이 있는가? T, P, n, m, Sigma, possible shift range, valid shift quantifier가 모두 있으면 좋습니다. 둘째, output convention이 있는가? L이 all valid shifts를 담는다고 말했는지 확인합니다. 셋째, algorithm-specific memory를 정확히 말했는가? Naive는 memory가 거의 없고 L invariant가 중심입니다. Rabin-Karp는 rolling hash value를 기억하지만 equality는 candidate입니다. FSM은 matched-prefix length st를 기억합니다. 넷째, runtime에서 excluded cost를 명시했는가? FSMMatching의 \(O(n)\)O(n)은 automaton construction 제외이고, Rabin-Karp는 candidate verification cost를 분리해야 합니다.

구두시험에서는 이 rubric을 더 짧게 씁니다. 답을 시작할 때 'Ich benutze 0-basierte Shifts'처럼 convention을 고정합니다. 알고리즘 이름을 말한 뒤 바로 invariant 또는 state meaning을 말합니다. Runtime을 말할 때 loop count나 scan count를 붙입니다. 마지막으로 trap을 하나 스스로 예방합니다. 예를 들어 Rabin-Karp 답안 끝에 'Bei gleicher Restklasse pruefe ich die Zeichen explizit, sonst koennte ein unechter Treffer auftreten'라고 붙이면 false-hit trap을 미리 막습니다. 이런 한 문장이 partial answer를 exam-ready answer로 바꿉니다.

• 정의를 빠짐없이 썼는가?
• 출력이 모든 유효 이동량인가?
• 알고리즘이 기억하는 상태를 정확히 설명했는가?
• 실행 시간에 전처리·구성 비용을 포함하는지 명시했는가?
• 대표 함정 하나를 미리 반박했는가?

좋은 답안은 정의, invariant/state, runtime, trap prevention이 모두 들어 있습니다.

출처에 근거한 범위와 자료의 한계(Source boundary)

이 페이지의 course-backed 핵심은 세 부분입니다. 첫째, Übung/AuD26_Sheet07-GrpSol.pdf pages 1-3은 \(\text{formal} \text{String}-\text{Matching}-\text{Problem}, \text{NaiveStringMatching} \text{pseudocode}, \text{invariant} \text{proof}, \text{runtime} O((n-m+1)m), \text{example} L=[0,6]\)formal String-Matching-Problem, NaiveStringMatching pseudocode, invariant proof, runtime O((n-m+1)m), example L=[0,6]을 제공합니다. 둘째, pages 4-6은 Rabin-Karp의 p, t0 계산, rolling update, modulo q, explicit verification, false hits를 제공합니다. 셋째, Sheet07 pages 12-13과 Sheet09 H1은 FSMMatching, state meaning, output shift, runtime without automaton construction을 제공합니다.

Gap도 명확히 남깁니다. 현재 확인한 corpus window에서는 full KMP failure table construction이 course material로 충분히 드러나지 않습니다. 따라서 KMP bounds와 failure-function intuition은 일반 알고리즘 지식으로 둡니다. 또한 FSM automaton construction cost는 Sheet09가 construction 제외 runtime을 묻기 때문에 이 페이지에서 확정하지 않습니다. 나중에 lecture slide나 exercise solution에서 exact construction rule and cost가 추가로 확인되면 이 chapter를 업데이트해야 합니다.

Source gap을 말하는 것은 약점이 아니라, unsupported course-specific claim을 피하는 안전장치입니다.