Cod sursa(job #1291240)

Utilizator akaprosAna Kapros akapros Data 12 decembrie 2014 16:41:13
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,p,q,k,nr,v[200005],w[200005],m;
char a[200005],b[200005];
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=a[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)
        sol[++sol[0]]=i-n;
        if (sol[0]==1000)
        break;
    }
    printf("%d\n",sol[0]);
    for (i=1;i<=sol[0];i++) printf("%d ",sol[i]);
    return 0;
}