Pagini recente » Cod sursa (job #2062566) | Cod sursa (job #916306) | Cod sursa (job #403523) | Cod sursa (job #2371697) | Cod sursa (job #3256077)
#include <iostream>
#include <vector>
using ll = long long;
#define int ll
using namespace std;
const int mod = 1e9 + 7, baza = 65;
vector <int> va;
int lgput(int n, int e) {
if (e == 0)
return 1;
int aux = lgput(n, e / 2);
if (e % 2) return ((aux * aux) % mod) * n % mod;
else return (aux * aux) % mod;
}
int pozitie(char c) {
if ('A' <= c && c <= 'Z')
return c - 65 + 1;
if ('a' <= c && c <= 'z')
return c - 97 + 1 + 26;
if ('0' <= c && c <= '9')
return c - 48 + 26 * 2 + 1;
}
struct HASH {
int init(string s, int r) {
int hash = 0, pb = 1;
for (int i = 0; i < r; i++) {
hash += pb * pozitie(s[i]);
hash %= mod;
pb *= baza;
pb %= mod;
}
return hash;
}
int sequence(int remove, int add, string s, int lh, int lg) {
lh -= pozitie(s[remove]);
lh = (lh * lgput(baza, mod - 2)) % mod;
lh = (lh + (pozitie(s[add]) * lgput(baza, lg)) % mod) % mod;
return lh;
}
};
signed main() {
string a, b;
cin >> a >> b;
HASH hash;
int ha = hash.init(a, a.size()), hc = hash.init(b, a.size()), ans = 0;
for (int i = a.size(); i < b.size(); i++) {
if (ha == hc)
ans++, va.push_back(i - a.size());
hc = hash.sequence(i - a.size(), i, b, hc, a.size() - 1);
}
if (ha == hc)
ans++, va.push_back(b.size() - 1);
cout << ans << '\n';
for (auto x : va)
cout << x << ' ';
}