Cod sursa(job #1636007)

Utilizator sulzandreiandrei sulzandrei Data 6 martie 2016 21:41:03
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
unordered_map<char,int> number;
string T,P;
vector< int > positions;
int d = 256,q = 6673,h;
void Preprocessing()
{
    /*int nr = 0;
    int freq[256];
    for(int i = 0 ; i <= 255 ; i ++)
        freq[i] = 0;
    for( const char& c : T)
        freq[(int)c] = 1;
    for( const char& c: P)
        freq[(int)c] = 1;
    for(char c = 'A' ; c <= 'Z' ; c++)
        if ( freq[(int)c])
            //cout<<"Caracterul "<<c<<" are valoarea "<<nr<<'\n',
            number[c] = nr++,d++;
    for(char c = 'a' ; c <= 'z' ; c++)
        if( freq[(int)c])
            //cout<<"Caracterul "<<c<<" are valoarea "<<nr<<'\n',
            number[c] = nr++,d++;
   // cout<<"q :" << q<<'\n';
    //cout<<"d :" << d<<'\n';*/
}
void Rabin_Karp()
{

    Preprocessing();
    int n = T.length();
    int m = P.length();
    int h = 1;
    for(int i = 0;  i < m -1 ; i ++)
        h = ( (h % q) * (d % q) ) % q;
    //h = d;
    //for(int i = 2 ; i <= m-1 ;  i++)
      //  h = h*d;
    //cout<<"n :" << n<<'\n' <<"m :"<<m<<"\n"<<"h :"<<h<<"\n";
    int p = 0 , ts = 0;
    for(int i = 0 ; i < m ; i++)
        p = ( d* p + P[i]) % q,
        ts = (d * ts + T[i]) % q;
    //for(int i = 0 ; i < m ; i++)
      //  p = (d *p + number[P[i]]),
        //ts = (d* ts + number[T[i]]);
    for(int s = 0 ; s <= n-m  ; s++)
    {
        //cout<<"s = "<<s+1<<'\n';
        //cout<<"p :"<<p<<'\n';
        //cout<<"ts:"<<ts<<"\n\n";
        if (p == ts)
        {
            bool ok  = true;
            for(int i = 0 ; i < m ;  i ++)
                if (P[i] != T[s+i])
                    ok = false;
            if(ok)
                //cout<<"Modelul apare cu deplasamentul "<<s+1<<'\n',
                positions.push_back(s);
        }
        if(s < n-m)
        {
            //cout<<"s ="<<s<<" =>din ts="<<ts<<" scadem prima cifra(caracterul \'"<<T[s+1]<<"\')care are valoarea "<<number[T[s+1]]<<" inmultita h="<<h<<'\n';
            //cout<<"(number[T[s+1]]*h)%q =="<<(number[T[s+1]] * h) % q<<'\n';
            int ts_plus_1 = ( d * (ts - (T[s] * h) )  + T[ s + m ] ) % q;
            ts = ts_plus_1;
            if( ts< 0)
                ts = ts +q;
        }
    }
}
int main()
{
    in >> P >> T;
    //cout << P <<"\n" << T << "\n";
    Rabin_Karp();
    out<<positions.size()<<'\n';
    for(int i  = 0 ; i < positions.size() ; i++)
        out<<positions[i]<<'\n';
    return 0;
}