Cod sursa(job #1277409)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 27 noiembrie 2014 17:10:03
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <string.h>
#define N 2000000
#define P 73
#define MOD1 100007
char A[N], B[N],match[N];
int main()
{
    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    int n=0,m=0;
    A[0]=fgetc(fin);
    while(A[n]!='\n')
        A[++n]=fgetc(fin);
    B[0]=fgetc(fin);
    while(B[m]!='\n'&&B[m]!=EOF)
        B[++m]=fgetc(fin);
    int P1=1,P2=1,hashA1=0,hashA2=0;
    int i,hash1=0;
    for(i=0;i<n;i++){
        hashA1=(hashA1*P+A[i])%MOD1;
        hash1=(hash1*P+B[i])%MOD1;
        if(i!=0)
            P1=(P1*P)%MOD1;
    }
    int nr=0;
    if(hash1==hashA1){
        match[0]=1;
        nr=1;
    }
    for(i=n;i<m;i++){
        hash1=((hash1-(B[i-n]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        if(hash1==hashA1){
            int pp=0,j=0;
            while(j<n&&pp==0){
                if(A[j]!=B[i-n+j+1])
                    pp=1;
                j++;
            }
            if(pp==0){
                match[i-n+1]=1;
                nr++;
            }
        }
    }
    fprintf(fout,"%d\n",nr);
    nr=0,i=0;
    while(i<m&&nr<1000){
        if(match[i]){
            fprintf(fout,"%d ",i);
            nr++;
        }
        i++;
    }
    return 0;
}