Pagini recente » Cod sursa (job #2451326) | Cod sursa (job #1350369) | Cod sursa (job #278898) | Cod sursa (job #1517252) | Cod sursa (job #2784189)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1 = 1e5 + 7;
const int MOD2 = 1e5 + 21;
const int BAZA = 73;
int main()
{
string s1, s2;
fin >> s1 >> s2;
int n1 = s1.size();
int n2 = s2.size();
int hash1_1 = 0, hash1_2 = 0;
int hash2_1 = 0, hash2_2 = 0;
vector<int> v;
if (n1 > n2)
{
cout << 0;
return 0;
}
int baza1 = 1, baza2 = 1;
for (int i = 0; i < n1; i++)
{
hash1_1 = (hash1_1 * BAZA + s1[i]) % MOD1;
hash1_2 = (hash1_2 * BAZA + s1[i]) % MOD2;
hash2_1 = (hash2_1 * BAZA + s2[i]) % MOD1;
hash2_2 = (hash2_2 * BAZA + s2[i]) % MOD2;
if (i != 0)
{
baza1 = (baza1 * BAZA) % MOD1;
baza2 = (baza2 * BAZA) % MOD2;
}
}
if (hash1_1 == hash2_1 && hash1_2 == hash2_2)
{
v.push_back(0);
}
for (int i = n1; i < n2; i++)
{
hash2_1 = ((hash2_1 - (s2[i - n1] * baza1) % MOD1 + MOD1) * BAZA + s2[i]) % MOD1;
hash2_2 = ((hash2_2 - (s2[i - n1] * baza2) % MOD2 + MOD2) * BAZA + s2[i]) % MOD2;
if (hash2_1 == hash1_1 && hash2_2 == hash1_2)
v.push_back(i - n1 + 1);
}
fout << v.size() << "\n";
for (int i = 0; i < v.size(); i++)
{
fout << v[i] << " ";
}
return 0;
}