Pagini recente » Cod sursa (job #3363175) | Cod sursa (job #3361364) | Cod sursa (job #3363218) | Cod sursa (job #3363187) | Cod sursa (job #3363210)
#include <bits/stdc++.h>
using namespace std;
const int BAZA = 67;
const int MOD = 1e9 + 7;
const int CIF_MAX = 1000000;
int inv[CIF_MAX + 1], v[CIF_MAX + 1];
long long h[CIF_MAX + 1];
int cod(char c)
{
if(c >= '0' && c <= '9')
{
return c - '0';
}
else if(c >= 'a' && c <= 'z')
{
return c - 'a' + 10;
}
else
{
return c - 'A' + 36;
}
}
int hs(string s, int b)
{
int put, nr = 1;
put = 1;
for(int i = 0; i < s.size(); i++)
{
nr = (1LL * nr + ((1LL * cod(s[i] - '0') * put) % MOD)) % MOD;
put = (1LL * put * b) % MOD;
}
return nr;
}
int hp(string s, int b)
{
int put = 1, nr = 1;
for(int i = 0; i < s.size(); i++)
{
nr = (1LL * nr + ((1LL * cod(s[i] - '0') * put) % MOD)) % MOD;
put = 1LL * put * b % MOD;
h[i + 1] = (1LL * h[i] + nr);
}
return nr;
}
int put(int a, int b)
{
if(b == 1)
return a;
if(b == 0)
return 1;
if(b % 2 == 1)
{
return 1LL * (1LL * put(1LL * a * a % MOD, b / 2) * a % MOD) * a % MOD;
}
else
{
int rez = put(a, b / 2);
return 1LL * rez * rez % MOD;
}
}
signed main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ha, hb, poz = 0, chb = 0, lenb = 0, ap = 0;
string a, b;
char c;
cin >> b >> a;
cin >> a >> b;
hb = hs(b, BAZA);
chb = hb;
while(chb > 0)
{
chb /= 10;
lenb++;
}
ha = hp(a, BAZA);
for(int i = 0; i <= CIF_MAX; i++)
{
inv[i] = put(BAZA, 1LL * i * (MOD - 2) % MOD);
}
lenb = b.size();
inv[0] = 1;
for(int i = lenb; i <= a.size(); i++)
{
if(1LL * (h[i] - h[i - lenb] + MOD) * inv[i - lenb + 1] % MOD == hb)
{
if(ap <= 1000)
v[ap++] = i - lenb + 1;
else
ap++;
}
}
cout << ap << "\n";
for(int i = 0; i < min(ap, 1000); i++)
{
cout << v[i] << " ";
}
//cout << (1LL * h[8] - h[5] + MOD) % MOD * inv[6] % MOD << " " << hb;
return 0;
}