Pagini recente » Cod sursa (job #2266341) | Cod sursa (job #2166646) | Cod sursa (job #648852) | Cod sursa (job #3150155) | Cod sursa (job #2589889)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int MOD = 1e9 + 9;
const int base = 256;
int putere(int x, int p)
{
int aux = 1;
while (p)
{
if (p % 2)
aux = (1ll * aux * x) % MOD;
x = (1ll * x * x) % MOD;
p /= 2;
}
return aux;
}
char s[2000005], p[2000005];
int hp, hs;
vector<int> sol;
int main()
{
cin >> p >> s;
int np = strlen(p);
for (int i = 0; i < np; i++)
{
hp = (1ll * hp * base + p[i]) % MOD;
hs = (1ll * hs * base + s[i]) % MOD;
}
int ns = strlen(s);
int pBase = putere(base, np - 1);
for (int i = 0; i < ns - np + 1; i++)
{
if (i != 0)
{
hs -= (1ll * s[i - 1] * pBase) % MOD;
hs = (hs + MOD) % MOD;
hs = (1ll * hs * base) % MOD;
hs = (hs + s[i + np - 1]) % MOD;
}
if (hs == hp)
{
int ok = 1;
for (int j = i; j < i + np; j++)
{
if (s[j] != p[j-i])
{
ok = 0;
break;
}
}
if (ok)
sol.push_back(i);
}
}
cout << sol.size() << '\n';
for (int i = 0; i < min(sol.size(),(unsigned)1000);i++)
cout << sol[i] << ' ';
return 0;
}