Pagini recente » Cod sursa (job #1021278) | Cod sursa (job #2409008) | Cod sursa (job #2200771) | Cod sursa (job #1989360) | Cod sursa (job #2558417)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
#define MOD1 100007
#define MOD2 100021
#define d 256
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void RabinKarp(string pattern, string text)
{
int pLenght = pattern.size();
int tLenght = text.size();
int p1 = 0;
int p2 = 0;
int t1 = 0;
int t2 = 0;
int dL1 = 1;
int dL2 = 1;
int cnt = 0;
vector<int> positions;
for(int i = 1; i < pLenght; i++)
{
dL1 = (dL1 * d) % MOD1;
dL2 = (dL2 * d) % MOD2;
}
for(int i = 0; i < pLenght; i++)
{
p1 = (d * p1 + pattern[i]) % MOD1;
p2 = (d * p2 + pattern[i]) % MOD2;
t1 = (d * t1 + text[i]) % MOD1;
t2 = (d * t2 + text[i]) % MOD2;
}
for(int i = 0; i < tLenght - pLenght && cnt < 1000; i++)
{
if(p1 == t1 && p2 == t2)
{
cnt++;
positions.push_back(i);
}
t1 = (d * (t1 - text[i] * dL1) + text[i + pLenght]) % MOD1;
t2 = (d * (t2 - text[i] * dL2) + text[i + pLenght]) % MOD2;
if(t1 < 0) t1 += MOD1;
if(t2 < 0) t2 += MOD2;
}
g<<cnt<<endl;
for(int i = 0; i < positions.size(); i++)
g<<positions[i]<<" ";
}
int main()
{
string pattern;
string text;
f>>pattern;
f>>text;
RabinKarp(pattern, text);
}