Cod sursa(job #1163900)

Utilizator ovidiu95Decean Ovidiu Ciprian ovidiu95 Data 1 aprilie 2014 18:24:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#define NMAX 2000010
using namespace std;
char A[NMAX],B[NMAX];
int i,q,n,m,aux,k,rez[10005],pi[NMAX];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s\n",A+1,B+1);
    m=strlen(A+1); n=strlen(B+1);
    for(i=2;i<=m;++i)
    {
        while(q && A[q+1]!=A[i]) q=pi[q];
        if(A[q+1]==A[i]) ++q;
        pi[i]=q;
    }
    q=0;
    for(i=1;i<=n;++i)
    {
        while(q && A[q+1]!=B[i]) q=pi[q];
        if(A[q+1]==B[i]) ++q;
        if(q==m)
        {
            q=pi[q];
            ++k;
            if(k<=10000) rez[k]=i-m;
        }
    }
    printf("%d\n",k);
    aux=min(k,10000);
    for(i=1;i<=aux;++i) printf("%d ",rez[i]);
    return 0;

}