Source code for submission s1151

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;
            }
        }
    }
}
*/

Diff to submission s1045

--- 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