Knuth–Morris–Pratt Algorithm

• 일반적인 bruteforce 패턴 판별
  • $O(N\ast M)$
• KMP는 접두사, 접미사로 문자열 일치 판별
  • $O(N+M)$
• Two Pointers 기법
  • j
    • 접두사 인덱스
    • i 위치의 값과 일치하면
      • +1하고, 그 값을 테이블에 저장
    • 불일치시
      • 마지막 일치 순간으로 j 이동
  • i
    • 접미사 인덱스
    • 한칸씩 이동하면서 일치 판별
  • table
    • 매칭 실패했을 때 어디까지 pattern index를 돌아갈지 정보가 담긴 배열
      • 이전 일치지점에서 시작
      • 0이라면 처음부터 다시 매칭
      • 값이 있다는건 그 값까지 이미 일치함을 보장

•   vector<int> make_table(const string& pattern){ // pi, prefix function, failure function
    	vector<int> table(pattern.size(), 0);
    	int j = 0;
    	
    	for (int i = 1; i < pattern.size(); ++i) {
    	
    		while (j > 0 && pattern[i] != pattern[j])
    			j = table[j - 1];
    			
    		if (pattern[i] == pattern[j])
    			table[i] = ++j;
    	}
    	
    	return table; 
    }
    /*
    vector<int> KMP_GET(string grope){
        int Begin=0, Length = (int)grope.size();
        vector<int> pi(Length, 0);
        for(int i=1 ; i< Length ; i++){
            while(grope[i] != grope[Begin] && Begin > 0)Begin = pi[Begin-1];
            if(grope[i] == grope[Begin]) pi[i] = ++Begin;
        }
        return pi;
    }
    */
    
    void KMP(const string& s, const string& needle){
    	vector<int> table = make_table(needle);
    	int s_size = s.size();
    	int needle_size = needle.size();
    	int j = 0;
    
    	for(int i = 0; i < s_size; ++i){
    		while (j > 0 && s[i] != needle[j])
    			j = table[j - 1];
    
    		if (s[i] == needle[j]){
    			if (j == needle_size - 1){
    				j = table[j];
    				// i - needle_size + 2 에서 매칭
    				// or i - j
    			}
    			else
    				++j;
    		}
    	}
    }