Cod sursa(job #1231685)

Utilizator thewildnathNathan Wildenberg thewildnath Data 21 septembrie 2014 12:54:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>
#include<string.h>

#define LMAX 2000005

int n, m;
char a[LMAX], b[LMAX];

int pia[LMAX], pib[LMAX], poz[1002];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    int sol=0, k;

    scanf("%s\n%s", a+1, b+1);

    n=strlen(a+1);
    m=strlen(b+1);

    pia[1]=k=0;

    for(int i=2; i<=n; ++i)
    {
        while(k && a[k+1] != a[i])
            k=pia[k];
        if(a[k+1] == a[i])
            ++k;

        pia[i]=k;
    }

    pib[1]=k=0;

    for(int i=1; i<=m; ++i)
    {
        while(k && a[k+1] != b[i])
            k=pia[k];
        if(a[k+1] == b[i])
            ++k;

        pib[i]=k;


        if(pib[i]==n)
        {
            ++sol;
            if(sol<=1000)
                poz[sol] = i-1;
        }
    }

    printf("%d\n", sol);

    int lim=1000;
    if(sol<1000)
        lim=sol;

    for(int i=1; i<=lim; ++i)
        printf("%d ", poz[i]-n+1);
    printf("\n");

    return 0;
}