Pagini recente » Cod sursa (job #295448) | Cod sursa (job #3214535) | Cod sursa (job #1997255) | Cod sursa (job #1392466) | Cod sursa (job #2566150)
#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod1 = 666013;
const int mod2 = 777013;
const int p = 27;
int p1=1, p2=1;
int hash1B=0, hash2B=0;
int hash1A=0, hash2A=0;
string a;
string b;
vector<int>sol;
int main()
{
getline(fin, a);
getline(fin, b);
int na = a.size();
int nb = b.size();
for (int i = 0; i < na; i++)
{
hash1A = ((hash1A * p) % mod1 + (a[i] - 'A')) % mod1;
hash2A = ((hash2A * p) % mod2 + (a[i] - 'A')) % mod2;
hash1B = ((hash1B * p) % mod1 + (b[i] - 'A')) % mod1;
hash2B = ((hash2B * p) % mod2 + (b[i] - 'A')) % mod2;
if (i != 0)
{
p1 *= p; p1 %= mod1;
p2 *= p; p2 %= mod2;
}
}
if (hash1A == hash1B && hash2A == hash2B)
sol.push_back(1);
for (int i = na ; i < nb ; i++)
{
hash1B = ((((hash1B - (b[i - na] - 'A') * p1 + mod1) % mod1) * p) % mod1 + (b[i] - 'A')) % mod1;
hash2B = ((((hash2B - (b[i - na] - 'A') * p2 + mod2) % mod2) * p) % mod2 + (b[i] - 'A')) % mod2;
if (hash1A == hash1B && hash2A == hash2B)
sol.push_back(i - na + 1);
}
fout << sol.size() << "\n";
int mi = min(1000, (int)sol.size());
for (int i = 0; i < mi; i++)
fout << sol[i] << " ";
return 0;
}