Pagini recente » Cod sursa (job #2028234) | Cod sursa (job #865969) | Cod sursa (job #1981412) | Cod sursa (job #229589) | Cod sursa (job #2768809)
#include <fstream>
#include <vector>
using namespace std;
const long long int modx = 1000000007;
const long long int mody = 1000000009;
int cnt;
string A, B;
vector < int > ans;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int exp(long long int b, long long int e, long long int mod) {
if (e == 0)
return 1;
if (!(e & 1))
return exp(((b % mod) * (b % mod)) % mod, (e >> 1), mod) % mod;
else
return ((b % mod) * (exp(((b % mod) * (b % mod)) % mod, (e >> 1), mod) % mod)) % mod;
}
long long int inv_mod(long long int a, long long int mod) {
return exp(a, mod - 2, mod) % mod;
}
long long int value(char x) {
if ('A' <= x && x <= 'Z')
return x - 'A';
if ('a' <= x && x <= 'z')
return x - 'a' + 26;
if ('0' <= x && x <= '9')
return x - '0' + 52;
}
int main() {
fin >> A >> B;
if (A.size() > B.size()) {
fout << "0";
return 0;
}
else {
long long int px = 1, py = 1, hashx = 0, hashy = 0, hx = 0, hy = 0;
for (int i = 0; i < A.size(); ++ i, px = (px * 62) % modx, py = (py * 62) % mody) {
hashx = (hashx % modx + (px * value(A[i])) % modx) % modx;
hashy = (hashy % mody + (py * value(A[i])) % mody) % mody;
}
int invx = inv_mod(62, modx), invy = inv_mod(62, mody);
for (int i = 0, px = 1, py = 1; i < A.size(); ++ i, px = (px * 62) % modx, py = (py * 62) % mody) {
hx = (hx % modx + (px * value(B[i])) % modx) % modx;
hy = (hy % mody + (py * value(B[i])) % mody) % mody;
}
px = (px * invx) % modx;
py = (py * invy) % mody;
if (hx == hashx && hy == hashy) {
++ cnt;
ans.push_back(0);
}
for (int i = A.size(); i < B.size(); ++ i) {
hx = (((hx - value(B[i - A.size()]) + modx) % modx * invx) % modx + (value(B[i]) * px) % modx) % modx;
hy = (((hy - value(B[i - A.size()]) + mody) % mody * invy) % mody + (value(B[i]) * py) % mody) % mody;
if (hx == hashx && hy == hashy) {
++ cnt;
ans.push_back(i - A.size() + 1);
}
}
fout << cnt << "\n";
for (int i = 0; i < min(1000, cnt); ++ i)
fout << ans[i] << " ";
}
return 0;
}