Knuth Morris Pratt (KMP)

KMP 알고리즘 복잡도 O(n + m) //n, m은 문자열 길이

A B A A B A C
      A B A A B A C
          A B A A B A C

j = 3, i = 6일 때 미스매치
j = F[j-1] 요것이 의미하는것은 문자열의 앞부분 ABA의 진 접두사,접미사가
일치하는 최대길이 즉 1 따라서 위와같이 문자열을 옮긴다.


[-] Collapse

//KMP string match

#include<iostream>
#include<string>
using namespace std;

int F[100000];//전처리 table

void failure_Function(string str){
    F[0] = 0;
    int i = 1;
    int j = 0;
    while (i < str.size()){
        if (str[i] == str[j]){
            F[i] = j + 1;
            i++;
            j++;
        }
        else if (j > 0){
            j = F[j - 1];
        }
        else{
            F[i] = 0;
            i++;
        }
    }
}
int KMP(string l, string s){
    int i = 0;
    int j = 0;
    while (i < l.size()){
        if (l[i] == s[j]){
            if (j == s.size() - 1) return i - j;
            else i++, j++;
        }
        else{
            if (j > 0) j = F[j - 1];
            else i++;
        }
    }
}
int main(){
    freopen("input.txt", "r", stdin);
    string l_str; //given string
    string s_str; //find string
    cin >> l_str >> s_str;
    failure_Function(s_str);
    cout << KMP(l_str, s_str);
}