Cod sursa(job #1388094)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 15 martie 2015 10:10:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cstring>
#define MAXL 2000005
using namespace std;

char a[MAXL], b[MAXL];
int n, m, P[MAXL], L, nr = 0;
int SOL[1005];
int i, j;

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

    fin>>a+1; n = strlen(a+1);
    fin>>b+1; m = strlen(b+1);

    P[1] = 0; L = 0;
    for(i=2;i<=n;i++){

        while( L != 0 && a[i] != a[L+1] )
            L = P[L];
        if( a[i] == a[L+1] ){ L++; P[i] = L; }

    }

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

        while( L != 0 && b[i] != a[L+1]  )
            L = P[L];
        if( b[i] == a[L+1] ) L++;

        if( L == n )
            if(nr<1000)
                SOL[ ++nr ] = i-n+1;
            else nr++;
    }

    fout<<nr<<"\n";
    for(i=1;i<=min(nr,1000);i++) fout<<SOL[i]-1<<" ";

    return 0;
}