Cod sursa(job #2207702)

Utilizator Horia14Horia Banciu Horia14 Data 26 mai 2018 14:03:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<cstring>
#define MAX_LEN 2000000
#define MAX_POS 1000
#define MOD1 24019
#define MOD2 27319
#define d 256
using namespace std;

char T[MAX_LEN+1], P[MAX_LEN+1];
int pos[MAX_POS], n, m, hashT1, hashT2, hashP1, hashP2, h1, h2, k;

int main() {
    int i;
    FILE *fin, *fout;
    fin = fopen("strmatch.in","r");
    fout = fopen("strmatch.out","w");
    fscanf(fin,"%s%s",P,T);
    n = strlen(T);
    m = strlen(P);
    h1 = h2 = 1;
    for(i = 0; i < m; i++) {
        hashT1 = (hashT1*d + T[i]) % MOD1;
        hashT2 = (hashT2*d + T[i]) % MOD2;
        hashP1 = (hashP1*d + P[i]) % MOD1;
        hashP2 = (hashP2*d + P[i]) % MOD2;
        if(i != m - 1) {
            h1 = (h1*d) % MOD1;
            h2 = (h2*d) % MOD2;
        }
    }
    for(i = 0; i <= n - m; i++) {
        if(hashT1 == hashP1 && hashT2 == hashP2) {
            if(k < MAX_POS)
                pos[k++] = i;
            else k++;
        }
        if(i < n - m) {
            hashT1 = (d*(hashT1 - T[i]*h1) + T[i+m]) % MOD1;
            hashT2 = (d*(hashT2 - T[i]*h2) + T[i+m]) % MOD2;
            if(hashT1 < 0)
                hashT1 += MOD1;
            if(hashT2 < 0)
                hashT2 += MOD2;
        }
    }
    fprintf(fout,"%d\n",k);
    if(k > MAX_POS)
        k = MAX_POS;
    for(i = 0; i < k; i++)
        fprintf(fout,"%d ",pos[i]);
    fprintf(fout,"\n");
    fclose(fin);
    fclose(fout);
    return 0;
}