Pagini recente » Cod sursa (job #430174) | Cod sursa (job #2175464) | Cod sursa (job #1936115) | Cod sursa (job #1309637) | Cod sursa (job #2669817)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s, pattern;
vector < int > pos;
void RabinKarp(string s, string pattern, vector < int > &pos)
{
const int base = 256;
const int mod = 2000000011;
int n = s.size();
int m = pattern.size();
int p = 1;
int hs = 0, hpattern = 0;
for (int i=0; i<m; i++)
{
hs = (1LL * hs * base + s[i]) % mod;
hpattern = (1LL * hpattern * base + pattern[i]) % mod;
if (i > 0)
p = (1LL * p * base) % mod;
}
if (hs == hpattern && pattern.compare(0, m, s, 0, m) == 0)
pos.push_back(0);
for (int i=m; i<n; i++)
{
hs = (((1LL * hs + mod - (1LL * p * s[i-m]) % mod) * base) + s[i]) % mod;
if (hs == hpattern && pattern.compare(0, m, s, i-m+1, m) == 0)
pos.push_back(i-m+1);
}
}
int main()
{
f >> pattern >> s;
RabinKarp(s, pattern, pos);
int n = pos.size();
g << n << "\n";
n = min(n, 1000);
for (int i=0; i<n; i++)
g << pos[i] << " ";
return 0;
}