Pagini recente » Cod sursa (job #896144) | Cod sursa (job #2865832) | Cod sursa (job #472973) | Cod sursa (job #852461) | Cod sursa (job #1896409)
#include <fstream>
#include <string>
#include <vector>
#define a 10
#define MOD1 1000003
#define MOD2 1000037
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
vector<int> v;
int nr;
int main()
{
fin >> s1;
fin >> s2;
if (s1.size() > s2.size())
{
fout << 0;
return 0;
}
long long hashA1 = 0, hashA2 = 0;
long long pow1 = 1, pow2 = 1;
for (int i = 0; i < s1.size(); i++)
{
hashA1 = (hashA1 * a % MOD1 + s1[i]) % MOD1, pow1 = pow1 * a % MOD2;
hashA2 = (hashA2 * a % MOD2 + s1[i]) % MOD2, pow2 = pow2 * a % MOD2;
}
long long hashB1 = 0, hashB2 = 0;
for (int i = 0; i < s1.size(); i++)
{
hashB1 = (hashB1 * a % MOD1 + s2[i]) % MOD1;
hashB2 = (hashB2 * a % MOD2 + s2[i]) % MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2)
nr++, v.push_back(0);
for (int i = s1.size(); i < s2.size(); i++)
{
hashB1 = (hashB1 * a % MOD1 - s2[i - s1.size()] * pow1 % MOD1 + s2[i]) % MOD1;
hashB2 = (hashB2 * a % MOD2 - s2[i - s1.size()] * pow2 % MOD2 + s2[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2)
nr++, v.push_back(i - s1.size() + 1);
}
fout << nr << '\n';
for (int i = 0; i < nr; i++)
fout << v[i] << ' ';
return 0;
}