Go to diff to previous submission
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> using namespace std; static int pi[1100]; /*void popn(string &s, int n) { for(int i = 0; i < n; i++) s.pop(); }*/ void compute_prefix(string &P) { int m = P.length() - 1; pi[1] = 0; int k = 0; for(int q=2; q <= m; q++) { while(k > 0 && P[k+1] != P[q]) { k = pi[k]; } if(P[k+1] == P[q]) { k = k+1; } pi[q] = k; } } void kmp_matcher(string &T, string &P) { int n = T.length() - 1; int m = P.length() - 1; int q = 0; for (int i = 1; i <= n; i++) { while(q > 0 && P[q + 1] != T[i]) { q = pi[q]; } if(P[q + 1] == T[i]) { q++; } if(q == m) { //cerr << i << " " << m << endl; T.erase(i - m, m); //cerr << T << endl; n -= m; i -= 2*m; q = pi[q]; if (i < 1) { i = 0; q = 0; } } } } int main() { uint cases; string pat; while (cin >> cases >> pat) { pat = " " + pat; getchar(); for (uint c = 0; c < cases; ++c) { string tex; getline(cin, tex); tex = " " + tex; kmp_matcher(tex, pat); printf("%s\n", tex.c_str() + 1); } } return 0; } /* * * void compute_prefix(string &P) { int m = P.length(); pi[1] = 0; int k = 0; for(int q=2; q <= m; q++) { while(k > 0 && P[k] != P[q-1]) { k = pi[k]; } if(P[k] == P[q-1]) { k = k+1; } pi[q] = k; } } void kmp_matcher(string &T, string &P) { int n = T.length(); int m = P.length(); int q = 0; for (int i = 1; i <= n; i++) { while(q > 0 && P[q] != T[i-1]) { q = pi[q]; } if(P[q] == T[i-1]) { q++; } if(q ==m ) { //cerr << i << " " << m << endl; T.erase(i-m, m); //cerr << T << endl; n = n-m; i -= 2*m-1; q = pi[q]; if (i < 1) { i = 0; q = 0; } } } } */
--- c4.s1045.cteam097.bugs.cpp.0.bugs.cpp +++ c4.s1151.cteam097.bugs.cpp.0.bugs.cpp @@ -15,13 +15,13 @@ void compute_prefix(string &P) { - int m = P.length(); + int m = P.length() - 1; pi[1] = 0; int k = 0; for(int q=2; q <= m; q++) { - while(k > 0 && P[k] != P[q-1]) { + while(k > 0 && P[k+1] != P[q]) { k = pi[k]; } - if(P[k] == P[q-1]) { + if(P[k+1] == P[q]) { k = k+1; } @@ -31,23 +31,27 @@ void kmp_matcher(string &T, string &P) { - int n = T.length(); - int m = P.length(); + int n = T.length() - 1; + int m = P.length() - 1; int q = 0; for (int i = 1; i <= n; i++) { - while(q > 0 && P[q] != T[i-1]) { + while(q > 0 && P[q + 1] != T[i]) + { q = pi[q]; } - if(P[q] == T[i-1]) { + if(P[q + 1] == T[i]) + { q++; } - if(q ==m ) { + if(q == m) + { //cerr << i << " " << m << endl; - T.erase(i-m, m); + T.erase(i - m, m); //cerr << T << endl; - n = n-m; - i -= 2*m-1; + n -= m; + i -= 2*m; q = pi[q]; - if (i < 1) { + if (i < 1) + { i = 0; q = 0; @@ -59,19 +63,68 @@ int main() { - string pat; uint cases; - string text; + + + string pat; while (cin >> cases >> pat) { + pat = " " + pat; getchar(); for (uint c = 0; c < cases; ++c) { - text = ""; - getline(cin, text); - kmp_matcher(text, pat); + string tex; + getline(cin, tex); + tex = " " + tex; - printf("%s\n", text.c_str()); + kmp_matcher(tex, pat); + + printf("%s\n", tex.c_str() + 1); } } return 0; -} \ No newline at end of file +} + +/* + * + * void compute_prefix(string &P) { + int m = P.length(); + pi[1] = 0; + int k = 0; + + for(int q=2; q <= m; q++) { + while(k > 0 && P[k] != P[q-1]) { + k = pi[k]; + } + if(P[k] == P[q-1]) { + k = k+1; + } + pi[q] = k; + } +} +void kmp_matcher(string &T, string &P) { + int n = T.length(); + int m = P.length(); + + int q = 0; + for (int i = 1; i <= n; i++) { + while(q > 0 && P[q] != T[i-1]) { + q = pi[q]; + } + if(P[q] == T[i-1]) { + q++; + } + if(q ==m ) { + //cerr << i << " " << m << endl; + T.erase(i-m, m); + //cerr << T << endl; + n = n-m; + i -= 2*m-1; + q = pi[q]; + if (i < 1) { + i = 0; + q = 0; + } + } + } +} +*/ \ No newline at end of file