• x의 접두부 : 문자열 x의 앞에 오는 부분 문자열
• 문자열 x의 크기가 k인 접두부를 x_k으로 표기한다. 즉, x_k  = x[1..k] 이다.
• x = “banana” 일 때, x₁=”b”, x₂=”ba”, x₃=”ban”, ... 이다.
• x의 접미부 : 문자열 x의 뒤에 오는 부분 문자열
• “e”, “le”, “ple” 등은 문자열 x = “apple” 의 접미부이다.

• 텍스트 : 길이가 n인 문자열 T
• 패턴 : 길이가 m인 문자열 P. 단, m<=n
  
• 텍스트 T와 패턴 P를 구성하는 알파벳들의 집합을 ∑로 표기한다.
• 예를 들어, T = “acaabc” 이고 P = “aab” 이면 ∑ = { a, b, c } 이다.

• ex) 텍스트 abababcabcabcdabccbaabdabcabcdabcd 에서 패턴 abcabcd를 찾는 문제

String Matching의 응용

int[] naivematch(char T[], int n, char P[], int m) {
    int output[n];
    for(int k = 0; k <= n-m; k++) {
        for(int j=1; j<=m; j++) {
            if(T[k+j] == P[j])
                output[k+j] = max(output[k+j], j+1);
                // output[s+j]에 더 큰 값이 이미 저장되어 있을 수 있으므로 max 함수 사용
            else
                break;
        }
    }
    return output;
}

• 안본 데부터 시작하면 못 찾는 경우가 생긴다.
• 
  
• 전체 문자열의 길이가 n, 찾으려는 문자열의 길이가 m일 때, 시간복잡도는 O(m(n-m))이다.

• Q : 유한한 개수의 상태(state)의 집합
• q₀ ∈ Q : 시작 상태
• A ⊆ Q : “받아들이는” 상태의 집합
•  ∑ : 입력 알파벳의 집합
• δ : Q x ∑ 에서 Q로 매핑되는 함수. M의 전이 함수라고 불린다.
  

• Φ(””) = q₀  (””는 빈 문자열을 의미)
• Φ(wa) = δ(Φ(w), a) (단, w는 ∑의 원소로 구성된 문자열이며 a는 ∑내의 문자이다)
• 두 문자열 x, y에 대해, x뒤에 y를 연결한 문자열은 xy로 표기한다. 위에서 wa는 w뒤에 문자 a를 연결한 문자열이다.

// O(|∑|m)
int[][] get_transition_fuction(char P[], int m, char[] ∑) {...}

// O(n)
int DFAmatch(char T[], int n, char P[], int m, char[] ∑) {
    int[][] table = get_transition_fuction(P, m, ∑);  // table[q][a] = δ(q, a)
    int s = 0;  // 오토마타의 상태
    for(int i=1; i<=n; i++) {
        output[i] = s = table[s][T[i]];  // δ(s, T[i])
    }
}

• 상태 집합 Q는 {0, 1, ..., m} 이다.
• 초기 상태 q₀는 0이다.
• 받아들이는 상태는 m 뿐이다. 즉, A = {m} 이다.
• 임의의 상태 q와 문자 a에 대해, 전이 함수 δ는 다음과 같다.
• δ(q, a) = σ(P_qa)

1. 임의의 문자열 x와 문자 a에 대해 σ(xa) <= σ(x) + 1 이다.

• 증명 :
• 
  
• σ(x) = k 라 하자.
  
• σ(xa) = r > k+1 라고 가정한다. 이때, P_r는 xa의 접미부가 된다.
• P_r의 끝과 xa의 끝에서 a를 삭제하면, P_r-1은 x의 접미부가 된다.
• r-1 > k 이므로, P_r-1은 P_k보다 긴 x의 접미부가 된다.
• 이는 σ(x) = k라는 전제와 모순이다.
• 따라서 r <= k + 1, 즉 σ(xa) <= σ(x) + 1 여야 한다.

• 증명 :
• 
  
• σ의 정의에 의하면, P_q는 x의 접미부이다.
  
• P_qa는 xa의 접미부이므로 σ(P_qa) <= σ(xa) 가 성립한다.  ...ㄱ
  
• σ(xa) = r 이라 하면 보조정리 1에 의해 r<=q+1 이다.
  
• P_qa는 xa의 접미부이고, P_r도 xa의 접미부이며, |P_r|<=|P_qa| 이므로, P_r은 P_qa의 접미부이다.
• 따라서 r <= σ(P_qa), 즉 σ(xa) <= σ(P_qa)이다.  ...ㄴ
• ㄱ, ㄴ을 종합하면 σ(xa) <= σ(P_qa) <= σ(xa), 즉 σ(xa) = σ(P_qa) 가 성립한다.

• Base : i = 0일 때, Φ(T₀) = q₀ = 0 = σ(T₀) 로 성립한다.
• Step : 어떤 정수 i에 대해 Φ(T_i) = σ(T_i)라 하면
• Φ(T_i+1) = Φ(T_iT[i+1]) = δ(Φ(T_i), T[i+1])       (→ Φ의 정의에 의해) 
  
• Φ(T_i) = σ(T_i) = q 라 하면, δ(Φ(T_i), T[i+1]) = δ(q, T[i+1]) = σ(P_qT[i+1])    (→ δ의 정의에 의해)
  
• 보조정리 2에 의해, σ(P_qT[i+1]) = σ(T_iT[i+1]) 이 성립한다.
• σ(T_iT[i+1]) = σ(T_i+1)이므로, Φ(T_i+1) = σ(T_i+1) 이다.