Cod sursa(job #1160193)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 30 martie 2014 12:45:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <cstdio>
#include <cstring>

#define DN 2000005
#define DM 1005
using namespace std;

int pi[DN],n,m,rez[DM];
char x[DN],y[DN];

void make_prefix(){

    int k = 0;
    pi[1] = 0;
    for(int i = 2;i<=n;++i){

        while( k && x[k + 1] != x[i])
            k = pi[k];

        if(x[ k + 1 ] == x[i])
            ++k;
        pi[i] = k;
    }
}
void find_ap(){

    int k = 0;
    for(int i=1;i<=m;++i){

        while( k && x[k + 1]!=y[i])
            k = pi[k];
        if( x[k + 1] == y[i])
            ++k;
        if( k == n ){

            rez[ ++rez[0]] = i - k;
            if(rez[0]==1000)
                return;
        }

    }
}
void write(){

    cout<<rez[0]<<"\n";
    for(int i=1;i<=rez[0];++i)
        cout<<rez[i]<<" ";
}

int main()
{
    freopen("strmatch.in","r", stdin);
    freopen("strmatch.out","w", stdout);
    scanf("%s %s",x+1,y+1);
    n = strlen(x + 1); m = strlen(y + 1);
    make_prefix();
    find_ap();
    write();

    return 0;
}