Cod sursa(job #1420688)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 18 aprilie 2015 20:39:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
// KMP - O(N+M)
#include <fstream>
#include <cstring>
#include <vector>
#define Nmax 2000099
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
 
int N, M;
char A[Nmax], B[Nmax];
vector<int> sol;

void KMP(char A[Nmax], char B[Nmax], vector<int> &sol) {
    int phi[Nmax], q, N = strlen(A), M = strlen(B); 
    for (int i = 1; i <= N; i++) {
      phi[i] = 0;
    }

    q = 0;
    phi[1] = 0;
    for(int i = 2; i <= N; ++i) {
      while(q && A[q+1] != A[i]) q = phi[q];
      if(A[q+1] == A[i]) ++q;
      phi[i]=q;
    }

    q = 0;
    for(int i = 1; i <= M; ++i) {
      while(q && A[q+1] != B[i]) q = phi[q];
      if(A[q+1] == B[i]) ++q;
      if(q == N) sol.push_back(i-N+1);
    }

}
int main() {
    f >> (A+1) >> (B+1);
    N = strlen(A+1);
    M = strlen(B+1);

    KMP(A+1, B+1, sol);

    g << sol.size() << '\n';
    for(int i = 0; i < min((int)sol.size(), 1000); ++i) g << sol[i] - 1 << ' ';
    g << '\n';
    f.close();g.close();
    return 0;
}