Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const ull mod = 1e9 + 289;
- const int p1 = 1000199, p2 = 1000289;
- vector<ull> deg1, deg2;
- ull get_hash1(int l, int r, vector<ull> &h) {
- return h[r] - h[l] * deg1[r - l];
- }
- ull get_hash2(int l, int r, vector<ull> &h) {
- return (h[r] + mod - h[l] * deg2[r - l] % mod) % mod;
- }
- int main() {
- fast
- // file_in
- // file_in_out
- int n, m;
- cin >> n >> m;
- vector<int> a(2 * n);
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- a[2 * n - i - 1] = a[i];
- }
- // считаем степени p
- deg1.resize(2 * n + 1); deg2.resize(2 * n + 1);
- deg1[0] = 1; deg2[0] = 1;
- for (int i = 0; i < 2 * n; ++i) {
- deg1[i + 1] = deg1[i] * p1;
- deg2[i + 1] = (deg2[i] * p2) % mod;
- }
- // считаем хеши
- vector<ull> h1(2 * n + 1), h2(2 * n + 1);
- h1[0] = 0; h2[0] = 0;
- for (int i = 0; i < 2 * n; ++i) {
- h1[i + 1] = h1[i] * p1 + a[i];
- h2[i + 1] = (h2[i] * p2 % mod + a[i]) % mod;
- }
- // сравниваем подстроки
- vector<int> ans;
- for (int i = 0; i <= n - i; ++i) {
- if (h1[i] == get_hash1(2 * n - 2 * i, 2 * n - i, h1) && h2[i] == get_hash2(2 * n - 2 * i, 2 * n - i, h2)) {
- ans.push_back(n - i);
- }
- }
- for (int i = (int)ans.size() - 1; i >= 0; --i) {
- cout << ans[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement