Cod sursa(job #622459)

Utilizator cristianalex81Cristian Alexandru cristianalex81 Data 17 octombrie 2011 23:14:43
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#include <string.h>
#define dim 2000001

char a[dim],b[dim];
int n,m,t,c[dim];

void rabin_karp()
{
    int i,j;
    for (i=0;i<n-m;i++)
        for (j=0;j<m;j++)
            if (a[i+j]==b[j])
            {
                c[i]++;
                if (c[i]==m)//total fit
                    t++;
            }
            else
                break;
}

int main()
{
    int i,j;
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s",b);
    scanf("%s",a);
    n = strlen(a);
    m = strlen(b);
    rabin_karp();
    printf("%d\n",t);
    for (i=0,j=0;(j<t)&&(j<1000);i++)
    {
        if (c[i]==m)
        {
            printf("%d ",i);
            j++;
        }
    }
    return 0;
}