Pagini recente » Cod sursa (job #2977683) | Cod sursa (job #1411122) | Cod sursa (job #1835854) | Cod sursa (job #1872027) | Cod sursa (job #2567135)
#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 = 73;
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])) % mod1;
hash2A = ((hash2A * p) % mod2 + (a[i])) % mod2;
hash1B = ((hash1B * p) % mod1 + (b[i])) % mod1;
hash2B = ((hash2B * p) % mod2 + (b[i])) % 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]) * p1 + mod1))%mod1) % mod1) * p) % mod1 + (b[i])) % mod1;
hash2B = ((((hash2B - (((b[i - na]) * p2 + mod2))%mod2) % mod2) * p) % mod2 + (b[i])) % 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;
}