Cod sursa(job #544025)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 28 februarie 2011 22:00:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <string.h>

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

void read()
{
    freopen("strmatch.in","r",stdin);
    a[0]=' ';fgets(a+1,2000020,stdin);n=strlen(a)-2;
    b[0]=' ';fgets(b+1,2000020,stdin);m=strlen(b)-2;
}

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 write()
{
    int i;
    freopen("strmatch.out","w",stdout);
    printf("%d\n",sol);
    if (sol>1000) sol=1000;
    for (i=1;i<=sol;++i) printf("%d ",s[i]);
}

int main()
{
    read();
    prefix();
    kmp();
    write();
    return 0;
}