Cod sursa(job #1158999)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 29 martie 2014 11:21:13
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, i, j, p[DIM], v[DIM], nr, q;
char a[DIM], b[DIM];

void prefix(){
    p[1]=0;
    for(i=2; i<=m; i++)
    {
        q=p[i]-1;
        while(b[i]!=b[q+1] && q!=0)
            q=p[q];
        if(b[i]==b[q+1])
            p[i]=q+1;
        else
            p[i]=0;
    }
}

void kmp(){
    q=0;
    for(i=1; i<=n; i++)
    {
        while(a[i]!=b[q+1] && q!=0)
            q=p[q];
        if(a[i]==b[q+1])
            q++;
        if(q==m)
        {
            v[++nr]=i-m;
            q=p[q];
        }
    }
}

int main(){
    f.get(b+1, DIM);
    f.get();
    f.get(a+1, DIM);
    n=strlen(a+1);
    m=strlen(b+1);
    prefix();
    kmp();
    g<<nr<<"\n";
    for(i=1; i<=nr; i++)
        g<<v[i]<<' ';
    g<<"\n";
    return 0;
}