Хеширование строк

mod = 9223372036854775807

# Модульная арифметика
def add(a, b):
    if a + b >= mod:
        return a + b - mod
    return a + b

def sub(a, b):
    if a - b < 0:
        return a - b + mod
    return a - b

def mul(a, b):
    return a * b % mod

p = 31
s1 = input()
n = len(s1)
s2 = input()
m = len(s2)

H = [0] * (n + 1)
PU = [0] * (n + 1)
PU[0] = 1

for i in range(n):
    x = ord(s1[i]) - ord('a') + 1
    H[i + 1] = add(mul(H[i], p), x)
    PU[i + 1] = mul(PU[i], p)

h = 0
for i in range(m):
    x = ord(s2[i]) - ord('a') + 1
    h = add(mul(h, p), x)

A = []
for i in range(m - 1, n):
    r = i
    l = r - m + 1
    if sub(H[r + 1], mul(H[l], PU[r - l + 1])) == h:
        A.append(l)

print(len(A))
print(*[x + 1 for x in A])

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 9223372036854775807;

ll add(ll a, ll b) {
    if (a + b >= mod) return a + b - mod;
    return a + b;
}

ll sub(ll a, ll b) {
    if (a - b < 0) return a - b + mod;
    return a - b;
}

ll mul(ll a, ll b) {
    return (__int128)a * b % mod;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    const ll p = 31;
    
    string s1, s2;
    cin >> s1 >> s2;
    
    ll n = s1.size();
    ll m = s2.size();
    
    vector<ll> H(n + 1, 0);
    vector<ll> PU(n + 1, 0);
    PU[0] = 1;
    
    for (ll i = 0; i < n; i++) {
        ll x = s1[i] - 'a' + 1;
        H[i + 1] = add(mul(H[i], p), x);
        PU[i + 1] = mul(PU[i], p);
    }
    
    ll h = 0;
    for (ll i = 0; i < m; i++) {
        ll x = s2[i] - 'a' + 1;
        h = add(mul(h, p), x);
    }
    
    vector<ll> A;
    for (ll i = m - 1; i < n; i++) {
        ll r = i;
        ll l = r - m + 1;
        if (sub(H[r + 1], mul(H[l], PU[r - l + 1])) == h) {
            A.push_back(l);
        }
    }
    
    cout << A.size() << "\n";
    for (ll x : A) {
        cout << x + 1 << " ";
    }
    
    return 0;
}