Cod sursa(job #1291257)

Utilizator akaprosAna Kapros akapros Data 12 decembrie 2014 17:02:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,p,q,k,nr,v[2000005],m;
char a[2000005],b[2000005];
int sol[1005];
void prefix()
{
    v[1]=0; k=0;
    for (i=2;i<=n;i++)
    {
        while ((k>0)&&(a[i]!=a[k+1])) k=v[k];
        if (a[i]==a[k+1]) k++;
        v[i]=k;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    prefix(); k=0;
    for (i=1;i<=m;i++)
    {
        while ((k>0)&&(b[i]!=a[k+1]))
        k=v[k];
        if (b[i]==a[k+1]) k++;
        if (k==n)
        {if (sol[0]>=1000)
        ++sol[0]; else sol[++sol[0]]=i-n;}
    }
    printf("%d\n",sol[0]);
    for (i=1;i<=sol[0];i++) printf("%d ",sol[i]);
    return 0;
}