Cod sursa(job #975749)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 21 iulie 2013 15:39:01
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#define KEY1 660013
#define KEY2 11213
using namespace std;

string x,y;
int rez[1005];

int get_val(char x)
{
    if(islower(x))
        return (x-'a')+1;
    return (x-'A')+27;
}

int main()
{
    int base=52,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+get_val(x[i]))%KEY1;
        pattern_hash2=(pattern_hash2*base+get_val(x[i]))%KEY2;

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

    for(int i=0;i<n;++i)
    {
        string_hash1=(string_hash1*base+get_val(y[i]))%KEY1;
        string_hash2=(string_hash2*base+get_val(y[i]))%KEY2;
    }
    if(string_hash1==pattern_hash1 && string_hash2==pattern_hash2)
        cout<<0<<endl;


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


        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;
}