Pagini recente » Cod sursa (job #2260212) | Cod sursa (job #2292600) | Cod sursa (job #1362178) | Cod sursa (job #2470481) | Cod sursa (job #3220866)
#include <fstream>
using namespace std;
#define int long long
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int ans;
int pattern, h;
int v[1005];
string s1, s2;
int P = 89;
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++)
{
pattern = (pattern + (((s1[i] - 'A' + 1) * lgput(P, i + 1)) % MOD)) % MOD;
//out<<(s1[i] - 'A' + 1) * lgput(P, i)<<'\n';
}
//out<<pattern;
for(int i = 0; i<=s2.size(); i++)
{
//out<<i<<" ";
if(i < s1.size())
{
h = (h + (((s2[i] - 'A' + 1) * lgput(P, i + 1)) % MOD)) % MOD;
}
else
{
h = (h * lgput(P, MOD - 2)) % MOD;
h = (h - (s2[i - s1.size()] - 'A' + 1)) % MOD;
while(h < 0)
{
h += MOD;
}
h = (h + (((s2[i] - 'A' + 1) * lgput(P, 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;
}