Cod sursa(job #1635993)

Utilizator sulzandreiandrei sulzandrei Data 6 martie 2016 21:32:56
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 2.72 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 = 0,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 + number[P[i]]) % q,
        ts = (d * ts + number[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 = -1 ; 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+1+i])
                    ok = false;
            if(ok)
                //cout<<"Modelul apare cu deplasamentul "<<s+1<<'\n',
                positions.push_back(s+1);
        }
        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 - (number[T[s+1]] * h) % q))%q  + number[T[ s + m + 1]] ) % q;
            //int ts_plus_1 = d *(ts - number[T[s+1]]*h) + number[T[s+m+1]] ;
            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;
}