Pagini recente » Cod sursa (job #1604264) | Cod sursa (job #1813791) | Cod sursa (job #1166559) | Cod sursa (job #2581308) | Cod sursa (job #2876560)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define cin f
#define cout g
const int MOD1 = 100007;
const int MOD2 = 100021;
const int p = 26;
int main()
{
string a, b;
cin >> a >> b;
int lna, lnb;
lna = a.size(), lnb = b.size();
int hash1_a = 0, hash2_a = 0;
int p1 = 1, p2 = 1;
for(int i=0;i<lna;i++)
{
hash1_a = (hash1_a * p + a[i]) % MOD1;
hash2_a = (hash2_a * p + a[i]) % MOD2;
if(i != 0)
{
p1 = (p1 * p) % MOD1;
p2 = (p2 * p) % MOD2;
}
}
if(lna > lnb)
{
cout<<0<<'\n';
return 0;
}
int hash1 = 0, hash2 = 0;
for(int i=0;i<lna;i++)
{
hash1 = (hash1 * p + b[i]) % MOD1;
hash2 = (hash2 * p + b[i]) % MOD2;
}
int ans = 0;
vector < int > poz;
poz.reserve(lnb);
if(hash1 == hash1_a and hash2 == hash2_a)
poz[ans ++] = 0;
for(int i=lna;i<lnb;i++)
{
hash1 = ((hash1 - (b[i - lna] * p1) % MOD1 + MOD1) * p + b[i]) % MOD1;
hash2 = ((hash2 - (b[i - lna] * p2) % MOD2 + MOD2) * p + b[i]) % MOD2;
if(hash1 == hash1_a and hash2 == hash2_a)
poz[ans ++] = i - lna + 1;
}
cout<<ans<<'\n';
for(int i=0;i<ans;i++)
cout<<poz[i]<<" ";
return 0;
}