Cod sursa(job #999556)

Utilizator toncuvasileToncu Vasile toncuvasile Data 20 septembrie 2013 19:15:46
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
#include<string>
#include<cmath>
using namespace std;

#define dimMAX 2000002;
#define p 73;
#define mod1 1000007;
#define mod2 1000021;
int match[2000002];
int main(){
    string A,B;
    ifstream inFile("strmatch.in");
    getline(inFile,A);
    getline(inFile,B);
    int a,b;
    a=A.size()-1;
    b=B.size()-1;
    ofstream outFile;
    outFile.open("strmatch.out");
    long long hashA=0,hash1A=0;
    long long hashB=0,hash1B=0;
    for(int i=0;i<=a;i++){
        hashA=2*hashA+A[i];
        hash1A=3*hash1A+A[i];
        hashB=2*hashB+B[i];
        hash1B=3*hash1B+B[i];
    }
    int nr=0;
    if(hashA==hashB && hash1A==hash1B){
            nr++;
            match[nr]=0;
    }
    long long power=pow(2,a+1);
    long long power1=pow(3,a+1);
    for(int i=1;i<=b-a;i++){
        hashB=2*hashB+B[i+a]-power*B[i-1];
        hash1B=3*hash1B+B[i+a]-power1*B[i-1];
        if(hashB==hashA && hash1B==hash1A){
            nr++;
            match[nr]=i;
        }
    }
    outFile<<nr<<"\n";
    if(nr>1000) nr=1000;
    for(int i=1;i<=nr;i++) outFile<<match[i]<<" ";

}