Untitled
c_cpp
24 days ago
896 B
2
Indexable
Never
/// KMP - O(N + M) /// Memory - O(M) #include <bits/stdc++.h> using namespace std; void computeLPSArray(string pat, int M, int *lps) { int len = 0; lps[0] = 0; int i = 1; while (i < M) { if (pat[i] == pat[len]) { ++len; lps[i] = len; ++i; } else { if (len != 0) len = lps[len - 1]; else lps[i] = 0, ++i; } } } void kmp(string txt, string pat) { int N = (int)txt.size(); int M = (int)pat.size(); int lps[M]; ///// computeLPSArray(pat, M, lps); int i = 0, j = 0; while ((N - i) >= (M - j)) { if (pat[j] == txt[i]) ++j, ++i; if (j == M) { cout<<"Found pattern at index "<<i - j<<'\n'; //////// j = lps[j - 1]; } else if (i < N && pat[j] != txt[i]) { if (j != 0) j = lps[j - 1]; else i = i + 1; } } } int main() { string txt = "abcabca"; string pat = "abc"; kmp(txt, pat); }