Pagini recente » Cod sursa (job #1723229) | Cod sursa (job #1585099) | Cod sursa (job #843568) | Cod sursa (job #1092303) | Cod sursa (job #1896468)
#include <fstream>
#include <vector>
#define LG 2000002
#define a 73
#define MOD1 100003
#define MOD2 100027
using namespace std;
ofstream fout("strmatch.out");
char s1[LG], s2[LG];
vector<int> v;
int main()
{
freopen("strmatch.in", "r", stdin);
scanf("%s %s", &s1, &s2);
int l1 = strlen(s1), l2 = strlen(s2);
if (l1 > l2)
{
fout << 0;
return 0;
}
long long hashA1 = 0, hashA2 = 0;
long long pow1 = 1, pow2 = 1;
for (int i = 0; i < l1; i++)
{
hashA1 = (hashA1 * a + s1[i]) % MOD1;
hashA2 = (hashA2 * a + s1[i]) % MOD2;
if (i > 0)
{
pow1 = pow1 * a % MOD1;
pow2 = pow2 * a % MOD2;
}
}
long long hashB1 = 0, hashB2 = 0;
for (int i = 0; i < l1; i++)
{
hashB1 = (hashB1 * a + s2[i]) % MOD1;
hashB2 = (hashB2 * a + s2[i]) % MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2)
v.push_back(0);
for (int i = l1; i < l2; i++)
{
hashB1 = ((hashB1 - s2[i - l1] * pow1 % MOD1 + MOD1) * a + s2[i]) % MOD1;
hashB2 = ((hashB2 - s2[i - l1] * pow2 % MOD2 + MOD2) * a + s2[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2)
v.push_back(i - l1 + 1);
}
fout << v.size() << '\n';
for (int i = 0; i < v.size(); i++)
fout << v[i] << ' ';
return 0;
}