Cod sursa(job #550646)

Utilizator mytzuskyMihai Morcov mytzusky Data 9 martie 2011 20:18:46
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <stdio.h>
#include <string.h>
#define Nmax 2000002
#define minim(a, b) ((a < b) ? a : b)

using namespace std;
char a[Nmax], b[Nmax];
int n,m,p[Nmax],pos[1001];

void Pref()
{
    int q=0;
    p[1]=0;

    for(int i=2;i<=m;i++)
    {
        while(q && a[q+1]!=a[i])
            q=p[q];
        if (a[q+1] == a[i])
            q++;
        p[i]=q;
    }
}


void ff()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    int q=0, k=0;
    scanf("%s%s",&a,&b);
    m = strlen(a);
    n = strlen(b);

    for(int i=m;i;i--) a[i] = a[i-1]; a[0] = ' ';
    for(int i=n;i;i--) b[i] = b[i-1]; b[0] = ' ';

    Pref();

    for(int i=1;i<=n;i++)
    {
        while (q && a[q+1] != b[i])
            q = p[q];
        if (a[q+1] == b[i])
            ++q;
        if (q == m)
        {
            q=p[m];
            k++;
            if(n<=1000)
                pos[k]=i-m;
        }
    }

    printf("%d\n", k);
    for (int i = 1; i <= minim(k, 1000); ++i)
        printf("%d ", pos[i]);
    printf("\n");
}

int main()
{
    ff();
    return 0;
}