Cod sursa(job #1495644)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 3 octombrie 2015 12:52:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<string.h>
#define N 2000005
char a[N+1],b[N+1];
int sol[1009],pi[N+1];
int main(){
    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    fgets(a+1,N,fin);
    fgets(b+1,N,fin);
    fclose(fin);
    int n=strlen(a+1),m=strlen(b+1);
    int k=0,i;
    n--,m--;
    for(i=2;i<=n;i++){
        while(k!=0&&a[i]!=a[k+1])
            k=pi[k];
        if(a[i]==a[k+1])
            k++;
        pi[i]=k;
        //printf("%d ",pi[i]);
    }
    int nr=0;
    k=0;
    for(i=1;i<=m;i++){
        while(k!=0&&b[i]!=a[k+1])
            k=pi[k];
        if(b[i]==a[k+1])
            k++;
        if(k==n&&nr<1000)
            sol[nr++]=i-n;
    }
    fprintf(fout,"%d\n",nr);
    if(nr>1000)
        for(i=0;i<1000;i++)
            fprintf(fout,"%d ",sol[i]);
    else
        for(i=0;i<nr;i++)
            fprintf(fout,"%d ",sol[i]);
    fclose(fout);
    return 0;
}