Pagini recente » Cod sursa (job #2785912) | Cod sursa (job #508436) | Cod sursa (job #1610733) | Cod sursa (job #1324075) | Cod sursa (job #3220871)
#include <fstream>
using namespace std;
#define int long long
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int ans;
int pattern, h;
int invp;
int putp[2000005];
int v[1005];
string s1, s2;
int P = 191;
int MOD = 1e9 + 9;
int lgput(int x, int e)
{
int ans = 1;
while(e != 0)
{
if(e % 2 == 1)
{
ans = (ans * x) % MOD;
}
x = (x * x) % MOD;
e /= 2;
}
return ans;
}
signed main()
{
in>>s1>>s2;
for(int i = 0; i<s1.size(); i++)
{
putp[i + 1] = lgput(P, i + 1);
pattern = (pattern + (((s1[i] - 'A' + 1) * putp[i + 1]) % MOD)) % MOD;
//out<<(s1[i] - 'A' + 1) * lgput(P, i)<<'\n';
}
invp = lgput(P, MOD - 2);
for(int i = 0; i<=s2.size(); i++)
{
//out<<i<<" ";
if(i < s1.size())
{
h = (h + (((s2[i] - 'A' + 1) * putp[i + 1]) % MOD)) % MOD;
}
else
{
h = (h * invp) % MOD;
h = (h - (s2[i - s1.size()] - 'A' + 1)) % MOD;
while(h < 0)
{
h += MOD;
}
h = (h + (((s2[i] - 'A' + 1) * putp[s1.size()]) % MOD)) % MOD;
while(h < 0)
{
h += MOD;
}
}
if(i >= s1.size() - 1)
{
//out<<i<<" ";
//out<<h<<" -> "<<pattern<<'\n';
if(h == pattern)
{
ans++;
if(ans <= 1000)
{
v[ans] = i - s1.size() + 1;
}
}
}
}
out<<ans<<'\n';
for(int i = 1; i<=min(1LL * 1000, ans); i++)
{
out<<v[i]<<" ";
}
return 0;
}