Cod sursa(job #552019)

Utilizator mytzuskyMihai Morcov mytzusky Data 11 martie 2011 15:30:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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 qq=0;
    p[1]=0;

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


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-1;i>=0;i--) a[i+1] = a[i];
    a[0] = ' ';
    for(int i=n-1;i>=0;i--) b[i+1] = b[i];
    b[0] = ' ';

    Pref();

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

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

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