Cod sursa(job #1159050)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 29 martie 2014 11:51:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string.h>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int i,p[2000001],q,n,m,s[2000001],nr;
char x,A[2000001],B[2000001],y,C[2000005];

int main()
{
    f >> B;
    f >> A;
    m = strlen(B);
    n = strlen(A);
    strcpy(C,A);
    strcpy(A+1,C);
    strcpy(C,B);
    strcpy(B+1,C);
     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;
    }
    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 ){
            s[++nr] = i - m;
            q = p[q];
        }
    }
    g << nr << '\n';
    if( nr > 1000)
        nr = 1000;
    for ( i = 1; i <= nr; i++)
        g << s[i] << " ";



    return 0;
}