Cod sursa(job #631604)

Utilizator geniucosOncescu Costin geniucos Data 8 noiembrie 2011 20:51:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#define abs(x) ((x>0)?x:x*-1)
#define max(a,b) ((a>b)?a:b)
#include<stdio.h>
#include<cstring>
using namespace std;
int i1,n,m,nr,d[2000001],phi[2000001];
char a[2000001],b[2000001];
int prefix()
{
    int k,i;
    k=0;
    phi[1]=0;
    for(i=2;i<=m;i++)
    {
        while(k!=0&&b[i]!=b[k+1]) k=phi[k];
        if(b[i]==b[k+1]) k++;
        phi[i]=k;
    }
}
int kmpp()
{
    int k,i;
    k=0;
    for(i=1;i<=n;i++)
    {
        while(k!=0&&a[i]!=b[k+1]) k=phi[k];
        if(a[i]==b[k+1]) k++;
        if(k==m)
        {
            nr++;
            if(nr<=1000) d[nr]=i-k;
            k=phi[k];
        }
    }
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b+1);
gets(a+1);
n=strlen(a+1);
m=strlen(b+1);
prefix();
kmpp();
if(nr>1000) nr=1000;
printf("%d\n",nr);
for(i1=1;i1<=nr;i1++)
    printf("%d ",d[i1]);
return 0;
}