Cod sursa(job #1376365)

Utilizator GilgodRobert B Gilgod Data 5 martie 2015 17:12:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

#define MAXL 2000000

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[MAXL+1], B[MAXL+1];
int PI[MAXL+1];
int n, m;
vector<int> pos;

void constr_prefix(){
// table:
/*
*   char: |a|b|a
*   index:|0|1|2
*   value:|0|0|1
*   for "abab" -> prefixes = {"aba", "ab", a"}
*              -> suffixes = {"bab", "ab", b"}
*/

    PI[1] = 0;
    int k = 0;
    for(int i = 1; i < n; i++) {
        while((k>0) && (A[k] != A[i])) k = PI[k];
        if(A[k] == A[i]) k++;
        PI[i] = k;
    }
}

int KMP(){
    int matched = 0;
    int k = 0;
    for(int i = 0; i < m; i++) {
        while((k > 0) && (A[k] != B[i])) k = PI[k-1];
        if(A[k] == B[i]) k++;
        if(k==n) {
            pos.push_back(i-n+1);
            matched++;
        }
    }
    return matched;
}

int main()
{
    fin >> A >> B;
    n = strlen(A);
    m = strlen(B);

    constr_prefix();
    fout<< KMP()<<endl;
    for(int i = 0; i < pos.size(); i++)
        fout<<pos[i]<< ' ';
    fout<<endl;
}