Cod sursa(job #793586)

Utilizator bogfodorBogdan Fodor bogfodor Data 3 octombrie 2012 16:17:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
#define lg 2000005

using namespace std;

FILE *fin=freopen("strmatch.in","r",stdin);
FILE *fout=freopen("strmatch.out","w",stdout);

char a[lg],b[lg];
int m,n,p[lg],sol[1001],k=0;

void read()
{
    scanf("%s\n%s",a,b);
    m=strlen(a);
    n=strlen(b);
}

void prefix()
{
    int i=0,j=-1;
    p[i]=j;
    while(i<m)
    {
    while(j>=0 && a[i]!=a[j])
        j=p[j];
        i++; j++;
        p[i]=j;
    }
}

void cauta()
{
    int i=0,j=0;
    while(i<n)
    {
        while(j>=0 && b[i]!=a[j])
            j=p[j];
        i++;
        j++;
        if(j==m)
        {
            if(k<1000)
                sol[k++]=i-j;
            else
                k++;
        j=p[j];
        }
    }
}

void print()
{
    printf("%d\n",k);
    for(int i=0; i<k && i<1000;i++)
        printf("%d ", sol[i]);
}

int main()
{
    read();
    prefix();
    cauta();
    print();
    return 0;
}