Pagini recente » Cod sursa (job #644350) | Cod sursa (job #1513063) | Cod sursa (job #2216733) | Cod sursa (job #2331627) | Cod sursa (job #3220890)
#include <fstream>
using namespace std;
#define int long long
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int ans;
int pattern1, pattern2;
int h1, h2;
int invp1, invp2;
int putp1[2000005];
int putp2[2000005];
int v[1005];
string s1, s2;
int P = 73;
int MOD1 = 1e9 + 7;
int MOD2 = 1e9 + 9;
int lgput(int x, int e, int MOD)
{
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++)
{
putp1[i + 1] = lgput(P, i + 1, MOD1);
pattern1 = (pattern1 + (((s1[i] - 'A' + 1) * putp1[i + 1]) % MOD1)) % MOD1;
putp2[i + 1] = lgput(P, i + 1, MOD2);
pattern2 = (pattern2 + (((s1[i] - 'A' + 1) * putp2[i + 1]) % MOD2)) % MOD2;
}
invp1 = lgput(P, MOD1 - 2, MOD1);
invp2 = lgput(P, MOD2 - 2, MOD2);
for(int i = 0; i<=s2.size(); i++)
{
//out<<i<<" ";
if(i < s1.size())
{
h1 = (h1 + (((s2[i] - 'A' + 1) * putp1[i + 1]) % MOD1)) % MOD1;
h2 = (h2 + (((s2[i] - 'A' + 1) * putp2[i + 1]) % MOD2)) % MOD2;
}
else
{
h1 = (h1 * invp1) % MOD1;
h1 = (h1 - (s2[i - s1.size()] - 'A' + 1)) % MOD1;
h2 = (h2 * invp2) % MOD2;
h2 = (h2 - (s2[i - s1.size()] - 'A' + 1)) % MOD2;
while(h1 < 0)
{
h1 += MOD1;
}
while(h2 < 0)
{
h2 += MOD2;
}
h1 = (h1 + (((s2[i] - 'A' + 1) * putp1[s1.size()]) % MOD1)) % MOD1;
h2 = (h2 + (((s2[i] - 'A' + 1) * putp2[s1.size()]) % MOD2)) % MOD2;
while(h1 < 0)
{
h1 += MOD1;
}
while(h2 < 0)
{
h2 += MOD2;
}
}
if(i >= s1.size() - 1)
{
//out<<i<<" ";
//out<<h<<" -> "<<pattern<<'\n';
if(h1 == pattern1 && h2 == pattern2)
{
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;
}