/**
Template by Akikaze (秋風) - formerly proptit_4t41.
Code written by a random fan of momocashew and Chiho.
**/
#include <bits/stdc++.h>
using namespace std;
/** -----BASIC MACROES----- **/
#define endl '\n'
#define i64 long long
#define ld long double
#define pub push_back
#define mp make_pair
#define fi first
#define se second
const long long MOD = 1000000007LL, INF = 1e9, LINF = 1e18;
const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
typedef vector<i64> vi;
typedef vector<ld> vd;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<i64, i64> pii;
typedef pair<i64, pii> pip;
typedef pair<pii, i64> ppi;
/** -----BIT CONTROLS----- **/
template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcount(s); }
/** -----IDEAS/ALGORITHMS-----
Hashing Algorithm (Multiple modules)
-------------------------- **/
/** -----CUSTOM TYPEDEFS/DEFINES----- **/
/** -----GLOBAL VARIABLES----- **/
i64 modArr[] = {(i64)1e9+3, (i64)1e9+7, (i64)1e8+3, (i64)1e8+7, (i64)1e7+7, (i64)1e7+3, (i64)1e6+3, (i64)1e6+7};
string A, B;
vector<vi> hashA;
i64 lenA, lenB;
vi hashKey(8, 0), hashMul(8, 1);
vi workingKey(8, 0);
/** -----EXTENSIVE FUNCTIONS----- **/
bool keyMatch() {
for (i64 i=0; i<8; i++) {
if (hashKey[i] != workingKey[i]) return false;
}
return true;
}
/** -----COMPULSORY FUNCTIONS----- **/
void VarInput() {
getline(cin, A); getline(cin, B);
lenA = A.size(); lenB = B.size();
hashA.resize(8, vi(lenA, 0));
// Initialize hashMul
for (i64 x=0; x<8; x++) {
for (i64 i=1; i<lenB; i++) hashMul[x] = (hashMul[x] * 257) % modArr[x];
}
// Calculate hashKey
for (i64 x=0; x<8; x++) {
for (i64 i=0; i<lenB; i++) hashKey[x] = (hashKey[x] * 257 + int(B[i])) % modArr[x];
}
// Pre-processing hashA array and workingKey
for (i64 x=0; x<8; x++) {
for (i64 i=0; i<lenA; i++) {
hashA[x][i] = int(A[i]);
if (i < lenB) workingKey[x] = (workingKey[x] * 257 + hashA[x][i]) % modArr[x];
}
}
}
void ProSolve() {
if (lenA < lenB) {
cout << ""; return;
}
// Prefix match
if (keyMatch()) cout << "1 ";
// Other subsequences
for (i64 i=1; i<=lenA-lenB; i++) {
for (i64 x=0; x<8; x++) {
workingKey[x] = (workingKey[x] - hashA[x][i-1] * hashMul[x]) % modArr[x];
while (workingKey[x] < 0) workingKey[x] += modArr[x];
workingKey[x] = (workingKey[x] * 257 + hashA[x][i+lenB-1]) % modArr[x];
}
if (keyMatch()) cout << (i+1) << " ";
}
cout << "";
}
/** -----MAIN FUNCTION----- **/
int main() {
//freopen("FILE.INP", "r", stdin);
//freopen("FILE.OUT", "w", stdout);
//ios_base::sync_with_stdio(0); cin.tie(NULL);
VarInput(); ProSolve(); return 0;
}
LyoqCglUZW1wbGF0ZSBieSBBa2lrYXplICjnp4vpoqgpIC0gZm9ybWVybHkgcHJvcHRpdF80dDQxLgoJQ29kZSB3cml0dGVuIGJ5IGEgcmFuZG9tIGZhbiBvZiBtb21vY2FzaGV3IGFuZCBDaGloby4KKiovCgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8qKiAtLS0tLUJBU0lDIE1BQ1JPRVMtLS0tLSAqKi8KI2RlZmluZSBlbmRsICdcbicKI2RlZmluZSBpNjQgbG9uZyBsb25nCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBwdWIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKY29uc3QgbG9uZyBsb25nIE1PRCA9IDEwMDAwMDAwMDdMTCwgSU5GID0gMWU5LCBMSU5GID0gMWUxODsKY29uc3QgbG9uZyBkb3VibGUgUEkgPSAzLjE0MTU5MjY1MzU4OTc5MzExNiwgRVBTID0gMWUtOSwgR09MRCA9ICgoMStzcXJ0KDUpKS8yKTsKdHlwZWRlZiB2ZWN0b3I8aTY0PiB2aTsKdHlwZWRlZiB2ZWN0b3I8bGQ+IHZkOwp0eXBlZGVmIHZlY3RvcjxzdHJpbmc+IHZzOwp0eXBlZGVmIHZlY3Rvcjxib29sPiB2YjsKdHlwZWRlZiBwYWlyPGk2NCwgaTY0PiBwaWk7CnR5cGVkZWYgcGFpcjxpNjQsIHBpaT4gcGlwOwp0eXBlZGVmIHBhaXI8cGlpLCBpNjQ+IHBwaTsKCi8qKiAtLS0tLUJJVCBDT05UUk9MUy0tLS0tICoqLwp0ZW1wbGF0ZTxjbGFzcyBUPiBpbnQgZ2V0Yml0KFQgcywgaW50IGkpIHsgcmV0dXJuIChzID4+IDEpICYgMTsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBUIG9uYml0KFQgcywgaW50IGkpIHsgcmV0dXJuIHMgfCAoVCgxKSA8PCBpKTsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBUIG9mZmJpdChUIHMsIGludCBpKSB7IHJldHVybiBzICYgKH4oVCgxKSA8PCBpKSk7IH0KdGVtcGxhdGU8Y2xhc3MgVD4gaW50IGNudGJpdChUIHMpIHsgcmV0dXJuIF9fYnVpbHRpbl9wb3Bjb3VudChzKTsgfQoKLyoqIC0tLS0tSURFQVMvQUxHT1JJVEhNUy0tLS0tCglIYXNoaW5nIEFsZ29yaXRobSAoTXVsdGlwbGUgbW9kdWxlcykKICAgIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tICoqLwoKLyoqIC0tLS0tQ1VTVE9NIFRZUEVERUZTL0RFRklORVMtLS0tLSAqKi8KCgovKiogLS0tLS1HTE9CQUwgVkFSSUFCTEVTLS0tLS0gKiovCmk2NCBtb2RBcnJbXSA9IHsoaTY0KTFlOSszLCAoaTY0KTFlOSs3LCAoaTY0KTFlOCszLCAoaTY0KTFlOCs3LCAoaTY0KTFlNys3LCAoaTY0KTFlNyszLCAoaTY0KTFlNiszLCAoaTY0KTFlNis3fTsKc3RyaW5nIEEsIEI7CnZlY3Rvcjx2aT4gaGFzaEE7Cmk2NCBsZW5BLCBsZW5COwp2aSBoYXNoS2V5KDgsIDApLCBoYXNoTXVsKDgsIDEpOwp2aSB3b3JraW5nS2V5KDgsIDApOwoKLyoqIC0tLS0tRVhURU5TSVZFIEZVTkNUSU9OUy0tLS0tICoqLwpib29sIGtleU1hdGNoKCkgewoJZm9yIChpNjQgaT0wOyBpPDg7IGkrKykgewoJCWlmIChoYXNoS2V5W2ldICE9IHdvcmtpbmdLZXlbaV0pIHJldHVybiBmYWxzZTsKCX0KCXJldHVybiB0cnVlOwp9CgovKiogLS0tLS1DT01QVUxTT1JZIEZVTkNUSU9OUy0tLS0tICoqLwp2b2lkIFZhcklucHV0KCkgewoJZ2V0bGluZShjaW4sIEEpOyBnZXRsaW5lKGNpbiwgQik7CglsZW5BID0gQS5zaXplKCk7IGxlbkIgPSBCLnNpemUoKTsKCWhhc2hBLnJlc2l6ZSg4LCB2aShsZW5BLCAwKSk7CgkKCS8vIEluaXRpYWxpemUgaGFzaE11bAoJZm9yIChpNjQgeD0wOyB4PDg7IHgrKykgewoJCWZvciAoaTY0IGk9MTsgaTxsZW5COyBpKyspIGhhc2hNdWxbeF0gPSAoaGFzaE11bFt4XSAqIDI1NykgJSBtb2RBcnJbeF07Cgl9CgkKCS8vIENhbGN1bGF0ZSBoYXNoS2V5Cglmb3IgKGk2NCB4PTA7IHg8ODsgeCsrKSB7CgkJZm9yIChpNjQgaT0wOyBpPGxlbkI7IGkrKykgaGFzaEtleVt4XSA9IChoYXNoS2V5W3hdICogMjU3ICsgaW50KEJbaV0pKSAlIG1vZEFyclt4XTsKCX0KCQoJLy8gUHJlLXByb2Nlc3NpbmcgaGFzaEEgYXJyYXkgYW5kIHdvcmtpbmdLZXkKCWZvciAoaTY0IHg9MDsgeDw4OyB4KyspIHsKCQlmb3IgKGk2NCBpPTA7IGk8bGVuQTsgaSsrKSB7CgkJCWhhc2hBW3hdW2ldID0gaW50KEFbaV0pOwoJCQlpZiAoaSA8IGxlbkIpIHdvcmtpbmdLZXlbeF0gPSAod29ya2luZ0tleVt4XSAqIDI1NyArIGhhc2hBW3hdW2ldKSAlIG1vZEFyclt4XTsKCQl9Cgl9Cn0KCnZvaWQgUHJvU29sdmUoKSB7CglpZiAobGVuQSA8IGxlbkIpIHsKCQljb3V0IDw8ICIiOyByZXR1cm47Cgl9CgkKCS8vIFByZWZpeCBtYXRjaAoJaWYgKGtleU1hdGNoKCkpIGNvdXQgPDwgIjEgIjsKCQoJLy8gT3RoZXIgc3Vic2VxdWVuY2VzCglmb3IgKGk2NCBpPTE7IGk8PWxlbkEtbGVuQjsgaSsrKSB7CgkJZm9yIChpNjQgeD0wOyB4PDg7IHgrKykgewoJCQl3b3JraW5nS2V5W3hdID0gKHdvcmtpbmdLZXlbeF0gLSBoYXNoQVt4XVtpLTFdICogaGFzaE11bFt4XSkgJSBtb2RBcnJbeF07CgkJCXdoaWxlICh3b3JraW5nS2V5W3hdIDwgMCkgd29ya2luZ0tleVt4XSArPSBtb2RBcnJbeF07CgkJCXdvcmtpbmdLZXlbeF0gPSAod29ya2luZ0tleVt4XSAqIDI1NyArIGhhc2hBW3hdW2krbGVuQi0xXSkgJSBtb2RBcnJbeF07CgkJfQoJCWlmIChrZXlNYXRjaCgpKSBjb3V0IDw8IChpKzEpIDw8ICIgIjsKCX0KCWNvdXQgPDwgIiI7Cn0KCi8qKiAtLS0tLU1BSU4gRlVOQ1RJT04tLS0tLSAqKi8KaW50IG1haW4oKSB7CgkvL2ZyZW9wZW4oIkZJTEUuSU5QIiwgInIiLCBzdGRpbik7CgkvL2ZyZW9wZW4oIkZJTEUuT1VUIiwgInciLCBzdGRvdXQpOwoJLy9pb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKE5VTEwpOwoJVmFySW5wdXQoKTsgUHJvU29sdmUoKTsgcmV0dXJuIDA7Cn0=