Cod sursa(job #1004984)

Utilizator thewildnathNathan Wildenberg thewildnath Data 3 octombrie 2013 21:17:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<stdio.h>
#include<string.h>
using namespace std;

int n,m,aux,c[2000002],poz[1002];
char a[2000002],b[2000002];

void fa(int i)
{
    while(a[aux+1]!=a[i]&&aux>0)
        aux=c[aux];
    if(a[aux+1]==a[i])
        ++aux;
}

void fb(int i)
{
    while(a[aux+1]!=b[i]&&aux>0)
        aux=c[aux];
    if(a[aux+1]==b[i])
        ++aux;
}

void prefix()
{
    int i;
    for(i=2;i<=n;++i)
    {
        fa(i);
        c[i]=aux;
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i,sol=0;
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    //////////////

    prefix();
    aux=0;
    for(i=1;i<=m;++i)
    {
        fb(i);
        if(aux==n)
        {
            aux=c[n];
            ++sol;
            if(sol<=1000)
                poz[sol]=i-n;
        }
    }

    //////////////
    printf("%d\n",sol);
    if(sol>1000)
        sol=1000;
    for(i=1;i<=sol;++i)
        printf("%d ",poz[i]);
    printf("\n");
    return 0;
}