Cod sursa(job #975753)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 21 iulie 2013 15:50:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#define KEY1 100007
#define KEY2 100021
using namespace std;

string x,y;
int rez[1005];

int main()
{
    int base=73,n,m;
    long long pattern_hash1=0,pattern_hash2=0,string_hash1=0,string_hash2=0,p1=1,p2=1;

    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    getline(f,x);
    getline(f,y);
    n=x.size();
    m=y.size();


    for(int i=0;i<n;++i)
    {
        pattern_hash1=(pattern_hash1*base+x[i])%KEY1;
        pattern_hash2=(pattern_hash2*base+x[i])%KEY2;

        p1=(p1*base)%KEY1;
        p2=(p2*base)%KEY2;
    }

    for(int i=0;i<n;++i)
        string_hash1=( string_hash1*base+y[i] ) % KEY1,
        string_hash2=( string_hash2*base+y[i] ) % KEY2;

    if(string_hash1==pattern_hash1 && string_hash2==pattern_hash2)
        rez[++rez[0]]=0;


    for(int i=n;i<m;++i)
    {
        string_hash1=((string_hash1*base - (y[i-n]*p1)%KEY1 + KEY1 ) +y[i])%KEY1;
        string_hash2=((string_hash2*base - (y[i-n]*p2)%KEY2 + KEY2 ) +y[i])%KEY2;

        //cout<<" I :"<<i<<" DDD "<<string_hash1<<" ->"<<pattern_hash1<<" | "<<string_hash2<<" ->"<<pattern_hash2<<endl;

        if(string_hash1==pattern_hash1 && string_hash2==pattern_hash2 && rez[0]<1000)
            rez[++rez[0]]=i-n+1;
    }
    g<<rez[0]<<"\n";
    for(int i=1;i<=rez[0];++i)
        g<<rez[i]<<" ";


    return 0;
}