Cod sursa(job #1000783)

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

#define dimMAX 2000002;
#define P 73
#define MOD1 100007
#define MOD2 100021

int match[2000002];
int p1=1,p2=1;
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;
    long long hashB=0;
    for(int i=0;i<=a;i++){
        hashA=(hashA*P+A[i])%MOD1;
        hashB=(hashB*P+B[i])%MOD1;
        if(i!=0) p1=(p1*P)%MOD1;
    }
    int nr=0;
    if(hashA==hashB){
            nr++;
            match[nr]=0;
    }
    for(int i=1;i<=b-a;i++){
        hashB=(((hashB-(p1*B[i-1])%MOD1+MOD1)%MOD1)*P+B[i+a])%MOD1;
        if(hashB==hashA){nr++;match[nr]=i; }
    }

    outFile<<nr<<"\n";
    if(nr>1000) nr=1000;
    for(int i=1;i<=nr;i++) outFile<<match[i]<<" ";

}