Cod sursa(job #995543)

Utilizator manutrutaEmanuel Truta manutruta Data 9 septembrie 2013 11:15:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <cstring>
using namespace std;

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

#define MAX 2000005
#define MAXM 1000
#define SIGMA 128
#define MOD1 100007
#define MOD2 100021

typedef unsigned long long int64;

char a[MAX],b[MAX];
int n,m,match[MAX],nm=0;

bool rabinKarp()
{
    if(m>n) {
        return 0;
    } else {
        unsigned p1=0,p2=0,t1=0,t2=0,h1=1,h2=1;

        for(int i=0; i<m; i++) {
            p1=(SIGMA*p1+b[i])%MOD1;
            p2=(SIGMA*p2+b[i])%MOD2;

            t1=(SIGMA*t1+a[i])%MOD1;
            t2=(SIGMA*t2+a[i])%MOD2;

            if(i!=0) {
                h1=(h1*SIGMA)%MOD1;
                h2=(h2*SIGMA)%MOD2;
            }
        }

        for(int s=0; s<=n-m; s++) {
            if(p1==t1&&p2==t2) {
                match[nm++]=s;
            }
            if(s<n-m) {
                t1=((t1-(a[s]*h1)%MOD1+MOD1)*SIGMA+a[s+m])%MOD1;
                t2=((t2-(a[s]*h2)%MOD2+MOD2)*SIGMA+a[s+m])%MOD2;
            }
        }
        return 1;
    }
}

int main()
{

    fgets(b,MAX,fin);
    fgets(a,MAX,fin);
    n=strlen(a)-1,m=strlen(b)-1;

    if(rabinKarp()) {
        fprintf(fout,"%d\n",nm);
        nm=(nm>MAXM)?MAXM:nm;
        for(int i=0; i<nm; i++) {
            fprintf(fout,"%d ",match[i]);
        }
        fputc('\n',fout);
    } else {
        fprintf(fout,"0\n");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}