Cod sursa(job #2059173)

Utilizator Horia14Horia Banciu Horia14 Data 6 noiembrie 2017 18:55:35
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<cstdio>
#include<cstring>
#define MAX_LEN 2000000
#define MAX_POS 1000
#define MOD 24019
#define d 256
using namespace std;

char T[MAX_LEN+1], P[MAX_LEN+1];
int pos[MAX_POS], hashT, hashP, h, k, n, m;

int main() {
    int i, j, l;
    bool ok;
    FILE *fin, *fout;
    fin = fopen("strmatch.in","r");
    fout = fopen("strmatch.out","w");
    fscanf(fin,"%s",P);
    fscanf(fin,"%s",T);
    n = strlen(T);
    m = strlen(P);
    h = 1;
    for(i=0; i<m; i++) {
        hashT = (d*hashT + T[i]) % MOD;
        hashP = (d*hashP + P[i]) % MOD;
        if(i != m - 1)
            h = (d*h) % MOD;
    }
    for(i=0; i<=n-m; i++) {
        if(hashT == hashP) {
            ok = true;
            for(j=0; j<m && ok; j++)
                if(T[i+j] != P[j])
                    ok = false;
            if(ok) {
                if(k < MAX_POS)
                    pos[k++] = i;
                else k++;
            }
        }
        if(i < n - m) {
            hashT = (d*(hashT - T[i]*h) + T[i+m]) % MOD;
            if(hashT < 0)
                hashT = (hashT + MOD);
        }
    }
    if(k < MAX_POS)
        l = k;
    else l = MAX_POS;
    fprintf(fout,"%d\n",k);
    for(i=0; i<l; i++)
        fprintf(fout,"%d ",pos[i]);
    fprintf(fout,"\n");
    fclose(fin);
    fclose(fout);
    return 0;
}