Cod sursa(job #501766)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 16 noiembrie 2010 16:22:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#include <string.h>

int n,m,v[2000001],s[1001],sol;
char a[2000001],b[2000001];

void rni()
{
    a[0]=' ';scanf("%s",a+1);n=strlen(a)-1;
    b[0]=' ';scanf("%s",b+1);m=strlen(b)-1;
}

void prefix()
{
    int i,p=0;
    for (i=2;i<=n;++i)
    {
        while (p&&(a[i]!=a[p+1])) p=v[p];
        if (a[i]==a[p+1])
        {
            ++p;
            v[i]=p;
        }
    }
}

void kmp()
{
    int i,p=0;
    for (i=1;i<=m;++i)
    {
        while (p&&(b[i]!=a[p+1])) p=v[p];
        if (b[i]==a[p+1])
        {
            ++p;
            if (p==n)
            {
                ++sol;
                if (sol<1001) s[sol]=i-p;
            }
        }
    }
}

void w()
{
    int i;
    printf("%d\n",sol);
    if (sol>1000) sol=1000;
    for (i=1;i<=sol;++i) printf("%d ",s[i]);
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    rni();
    prefix();
    kmp();
    w();
    return 0;
}