Pagini recente » Cod sursa (job #2201969) | Cod sursa (job #1144271) | Cod sursa (job #146601) | Cod sursa (job #1580418) | Cod sursa (job #3348960)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long mod1 = 1000000007;
const long long mod2 = 1000000009;
const long long baza = 67676767;
int main()
{
string a, b;
fin >> a >> b;
int n = a.size();
int m = b.size();
if (n > m)
{
fout << 0 << '\n';
return 0;
}
long long hashA1 = 0, hashA2 = 0;
long long hashB1 = 0, hashB2 = 0;
long long put1 = 1, put2 = 1;
for (int i = 0; i < n; i++)
{
hashA1 = (hashA1 * baza + a[i]) % mod1;
hashA2 = (hashA2 * baza + a[i]) % mod2;
hashB1 = (hashB1 * baza + b[i]) % mod1;
hashB2 = (hashB2 * baza + b[i]) % mod2;
if (i < n - 1)
{
put1 = put1 * baza % mod1;
put2 = put2 * baza % mod2;
}
}
vector<int> rez;
int cnt = 0;
if (hashA1 == hashB1 && hashA2 == hashB2)
{
cnt++;
rez.push_back(0);
}
for (int i = n; i < m; i++)
{
hashB1 = (hashB1 - b[i - n] * put1 % mod1 + mod1) % mod1;
hashB1 = hashB1 * baza % mod1;
hashB1 = (hashB1 + b[i]) % mod1;
hashB2 = (hashB2 - b[i - n] * put2 % mod2 + mod2) % mod2;
hashB2 = hashB2 * baza % mod2;
hashB2 = (hashB2 + b[i]) % mod2;
if (hashA1 == hashB1 && hashA2 == hashB2)
{
cnt++;
if ((int)rez.size() < 1000)
{
rez.push_back(i - n + 1);
}
}
}
fout << cnt << '\n';
for (auto x : rez)
{
fout << x << ' ';
}
return 0;
}