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

// Khai báo 2 bộ modulo nguyên tố đủ lớn để tránh collision
const long long MOD1 = 1e9 + 7;
const long long MOD2 = 1e9 + 9;

// Khai báo 2 cơ số (Base) lớn hơn kích thước bảng chữ cái (thường dùng số nguyên tố > 256)
const long long BASE1 = 311;
const long long BASE2 = 317;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string A = "ababcabcabababa";
    string B = "aba";

    int n = A.length();
    int m = B.length();


    // Tiền xử lý mảng lũy thừa cơ số
    vector<long long> pow1(n + 1, 1), pow2(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        pow1[i] = (pow1[i - 1] * BASE1) % MOD1;
        pow2[i] = (pow2[i - 1] * BASE2) % MOD2;
    }

    // Tiền xử lý mảng Hash tiền tố cho xâu A
    // h1[i] lưu hash của tiền tố A[0...i-1]
    vector<long long> h1(n + 1, 0), h2(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        h1[i + 1] = (h1[i] * BASE1 + A[i]) % MOD1;
        h2[i + 1] = (h2[i] * BASE2 + A[i]) % MOD2;
    }

    // 3. Tính giá trị Hash kép cho xâu mẫu B
    long long hashB1 = 0, hashB2 = 0;
    for (int i = 0; i < m; ++i) {
        hashB1 = (hashB1 * BASE1 + B[i]) % MOD1;
        hashB2 = (hashB2 * BASE2 + B[i]) % MOD2;
    }


    // Duyệt qua tất cả cửa sổ độ dài m trong xâu A để so sánh
    cout << "Xau A: " << A << "\n";
    cout << "Xau B: " << B << "\n";
    cout << "Cac vi tri xau B xuat hien trong A (0-indexed):\n";

    vector<int> matches;
    for (int i = 0; i <= n - m; ++i) {
        // Lấy Hash của đoạn A[i ... i + m - 1]
        long long res1 = (h1[i + m] - (h1[i] * pow1[m]) % MOD1 + MOD1) % MOD1;
        long long res2 = (h2[i + m] - (h2[i] * pow2[m]) % MOD2 + MOD2) % MOD2;

        // So sánh đồng thời cả 2 giá trị Hash
        if (res1 == hashB1 && res2 == hashB2) {
            matches.push_back(i);
        }
    }

    // In kết quả
    for (int pos : matches) {
        cout << "Vi tri " << pos << " -> " << A.substr(pos, m) << "\n";
    }

    return 0;
}