Pagini recente » Cod sursa (job #2408098) | Cod sursa (job #3286898) | Cod sursa (job #1890517) | Cod sursa (job #1798627) | Cod sursa (job #1635993)
#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;
}