Cod sursa(job #1981093)

Utilizator DragosArseneDragos Arsene DragosArsene Data 14 mai 2017 19:18:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char s1[2000001], s2[2000001], j;
int pozitii[2000001];
int baza[65];
int main() {
    FILE *fin, *fout;
    int n, hash1, hash2, key1=0, key2=0, x, q1, q2, key1test=0, key2test=0, contor=0, lung, i;
//63
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
hash1=786433;
hash2=572869;
fscanf(fin,"%s", &s1);
fscanf(fin,"%s", &s2);

n=strlen(s1);
x=1;

lung=strlen(s2);
for(i=n;i>=1;i--){
    s1[i]=s1[i-1];
}
for(i=lung;i>=1;i--){
    s2[i]=s2[i-1];
}
for(j='a';j<='z';j++){
    i=j;
    baza[j]=x;
    x++;
}

for(j='A';j<='Z';j++){
    i=j;
    baza[i]=x;
    x++;
}
for(i=0;i<=9;i++){
    baza[i]=x;
    x++;
}
q1=1;
q2=1;

for(i=n;i>=1;i--){
    key1=(key1+baza[s1[i]]*q1)%hash1;
    q1=q1*63%hash1;
    key2=(key2+baza[s1[i]]*q2)%hash2;
    q2=q2*63%hash2;
}
q1=1;
q2=1;

for(i=n;i>=1;i--){
    key1test=(key1test+baza[s2[i]]*q1)%hash1;
    q1=q1*63%hash1;
    key2test=(key2test+baza[s2[i]]*q2)%hash2;
    q2=q2*63%hash2;
}
x=1;
if(key1test==key1&&key2test==key2){
    contor++;
    pozitii[x]=i;
    x++;
}

q1=q1/63;
q2=q2/63;

for(i=n+1;i<=lung;i++){

    key1test=((key1test-baza[s2[i-n]]*q1)*63+baza[s2[i]]+hash1)%hash1;
    key2test=((key2test-baza[s2[i-n]]*q2)*63+baza[s2[i]]+hash2)%hash2;

    if(key1test==key1&&key2test==key2){
    contor++;
    pozitii[x]=i-n;
    x++;
    }
}
fprintf(fout,"%d\n", contor);
for(i=1;i<x;i++){
    fprintf(fout,"%d ", pozitii[i]);
}
fclose(fin);
fclose(fout);
    return 0;
}