KMP(Knuth-Morris-Pratt)

: 대표적인 문자열(string) 매칭 알고리즘

단순하게 모든 경우를 다 비교하면 O(n^2)의 시간이 들 수 있음. KMP알고리즘은 모든 경우를 다 비교하지 않더라도 부분 문자열을 찾을 수 있음.

매칭에 실패했을 때 얼마나 점프할 수 있을지를 접두사와 접미사로 알아낼 수 있음.
예를 들어 문자열이 abacaaba라고 할 때 접두사는 aba, 접미사는 aba라고 할 수 있음. 이 때 접두사와 접미사가 일치하는 최대 길이를 알아내야 함.
접두사와 접미사를 구하면 그 두개가 일치하는 경우에 한해 점프할 수 있어 효율적

참고 영상 https://www.youtube.com/watch?v=yWWbLrV4PZ8

j와 i의 문자가 일치한다면 i인덱스에 (j인덱스)+1를 넣어 테이블을 만듦.
일치하지 않는다면 j의 위치를 뒤로 한칸 옮겨줌.
(patternedSize = 찾고자하는 문자열의 길이)
결과값으로는 접두사 및 접미사의 최대 길이를 반환

접두사와 접미사를 하나씩 늘려 비교하며 일치하지 않는 경우가 발생하면 일치했던 부분까지 되돌아가 다시 검사를 반복함으로써 최대 일치 길이 테이블을 구축

문자열이 불일치한 인덱스에서 1을 뺀 값이 가리키는 그 값으로 j라는 인덱스를 이동시켜 다시 확인할 수 있도록
i인덱스는 하나씩 증가시키기만 하면 되므로 O(n) 시간복잡도를 가짐.

vector<int> makeTable(string pattern) {
  int patternSize = pattern.size();
  vector<int> table(patternSize, 0);
  int j = 0;

  for(int i=1; i<patternSize; i++) {
    while(j>0 && pattern[i]!=pattern[j]) {
      j = table[j-1];
    }
    if(pattern[i] == pattern[j]) {
      table[i] = j++;
    }
  }

  return table;
}

void KMP(string parent, string pattern) {
  vector<int> table = makeTable(pattern);
  int parentSize = parent.size();
  int patternSize = pattern.size();
  int j = 0;
  for(int i=0; i<parentSize; i++) {
    while(j>0 && parent[i]!=pattern[j]) {
      j = table[j-1];
    }
    if(parent[i] == pattern[j]) {
      if(j == patternSize-1) {
        cout << i-patternSize+2 << "번째에서 찾았습니다" << '\n';
        j = table[j];
      } else {
        j++;
      }
    }
  }
  cout << cnt << '\n';
}

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&proxyReferer=https:%2F%2Fwww.google.com%2F