Pagini recente » Cod sursa (job #2332950) | Statistici Catinas Daria Maria (BloodywolfDaria) | Istoria paginii utilizator/turcu_george_alexandru_321cb | Monitorul de evaluare | Cod sursa (job #1679984)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <string.h>
#define NMAX 1000
using namespace std;
static const int MOD = 2000011;
static const int MOD2 = 2000001;
static const int base = 256;
string Pattern, String;
vector<int> Sol;
int stringSize, patternSize;
void Read();
void Rabin_Karp();
void Write();
int main()
{
Read();
Rabin_Karp();
Write();
return 0;
}
void Write()
{
cout << Sol.size() << '\n'; //Number of matches
for(int i = 0; i < Sol.size() && i < 1000; ++i)
cout << Sol[i] << ' ';
}
void Rabin_Karp()
{
unsigned long base_M_minus_1, hashP, hashS;
unsigned long base_M_minus_12, hashP2, hashS2;
base_M_minus_1 = 1;
base_M_minus_12 = 1;
if(patternSize > stringSize)
return;
hashP = hashS = 0;
hashP2 = hashS2 = 0;
for(int i = 0; i < patternSize; ++i) {
hashP = (hashP * base + (Pattern[i] - 48) ) % MOD;
hashS = (hashS * base + (String[i] - 48) ) % MOD;
hashP2 = (hashP2 * base + (Pattern[i] - 48) ) % MOD2;
hashS2 = (hashS2 * base + (String[i] - 48) ) % MOD2;
if( i > 0 ) {
base_M_minus_1 = (base_M_minus_1 * base ) % MOD;
base_M_minus_12 = (base_M_minus_12 * base ) % MOD2;
}
}
for(int i = patternSize; i <= stringSize; ++i) {
if(hashS == hashP && hashS2 == hashP2)
//if(String.compare(i - patternSize, patternSize, Pattern) == 0) //Match
Sol.push_back(i - patternSize);
hashS = ( hashS + ( base * MOD ) - ( ( String[i - patternSize] - 48 ) * base_M_minus_1 ) ) % MOD;
hashS = ( hashS * base + String[i] - 48 ) % MOD;
hashS2 = ( hashS2 + ( base * MOD2 ) - ( ( String[i - patternSize] - 48 ) * base_M_minus_12 ) ) % MOD2;
hashS2 = ( hashS2 * base + String[i] - 48 ) % MOD2;
}
}
void Read()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
cin >> Pattern >> String;
patternSize = Pattern.size();
stringSize = String.size();
}