-
(라이님 블로그 대회 알고리즘 따라잡기 31) KMP(Knuth–Morris–Pratt Algorithm)PROGRAMMING/알고리즘 2024. 7. 31. 11:08
오늘은 KMP 알고리즘에 대해 공부해보았다. 솔직히 개념 + 코드 이해하는데 좀 걸렸다...
뭔가 직관적이지 않아서 이해가 단번에 되지 않았다..ㅠ
늘 그렇듯 설명은 라이님 블로그에 있다.(아휴 어려워)
그래도 보다보니 이해가 되는거 같기도 하다...^^
#include <iostream> #include <string> #include <vector> using namespace std; int main() { string S, W; getline(cin, S); getline(cin, W); int N = S.length(); int M = W.length(); // Fail function computation directly in main vector<int> fail(M, 0); // 0으로 초기화된 벡터 생성 for (int i = 1, j = 0; i < M; i++) { while (j > 0 && W[i] != W[j]) j = fail[j - 1]; if (W[i] == W[j]) { fail[i] = ++j; } } // KMP algorithm vector<int> result; for (int i = 0, j = 0; i < N; i++) { while (j > 0 && S[i] != W[j]) j = fail[j - 1]; if (S[i] == W[j]) { if (j == M - 1) { result.push_back(i - M + 2); // +1 for 1-based index j = fail[j]; } else { j++; } } } cout << result.size() << endl; for (int i : result) cout << i << " "; cout << endl; return 0; }
'PROGRAMMING > 알고리즘' 카테고리의 다른 글
(라이님 블로그 대회 알고리즘 따라잡기 32) Trie (0) 2024.08.05 (백준 4354번 문자열 제곱) (라이님 블로그 대회 알고리즘 따라잡기 31) KMP(Knuth–Morris–Pratt Algorithm) (0) 2024.08.01 (라이님 블로그 대회 알고리즘 따라잡기 30) LCA(Lowest Common Ancestor) (0) 2024.07.29 (라이님 블로그 대회 알고리즘 따라잡기 28) 디닉 알고리즘(Dinic's Algorithm) (4) 2024.07.23 (라이님 블로그 대회 알고리즘 따라잡기 26) 이분매칭(Bipartite Matching) (0) 2024.07.22