Cod sursa(job #613541)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 29 septembrie 2011 13:22:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<cstdio>
#include<cstring>
using namespace std;
int i,N,M,phi[100001],k,nr=0,a[100001];
char x[100001],s[100001];

void prefix()
{ int i,k;
    k=0; phi[1]=0;
    for (i=2;i<=N;i++)
    {
        while (k!=0 && x[i]!=x[k+1]) k=phi[k];
        if (x[i]==x[k+1]) k++;
        phi[i]=k;
    }
}

void kmp ()
{
    int i,k=0;
    for (i=1;i<=M; i++)
    {
        while(k!=0 && s[i]!=x[k+1]) k=phi[k];
        if (x[k+1]==s[i]) k++;
        if (k==N)
        {
            nr++;
            a[nr]=i-k;
            k=phi[k];
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(x+1);
    gets(s+1);
    M=strlen(s+1);N=strlen(x+1);
    prefix();
    kmp();
    printf("%d\n",nr);
    for (i=1;i<=nr;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}