#include <iostream>
#include <string>
#include <vector>
#define CLEN 256
using namespace std;

template <typename T>
std::vector< std::vector<T> > makeMatrix(int row, int col) 
{
    std::vector< std::vector<T> > vv(row);
    for(auto it=vv.begin();it!=vv.end();it++){
        (*it).resize(col);
    }
    return vv; 
}

vector< vector<int> > makeBadCTable(string pattern) 
{
    int plen=pattern.size();
    vector< vector<int> > table = makeMatrix<int>(plen,CLEN);

    for(int i=0;i<plen;i++){
    for(int j=0;j<CLEN;j++){
        table[i][j]=-1;
    }}

    for(int i=0;i<plen;i++){
        char c = pattern[i];
        for(int j=i+1;j<plen;j++){
            table[j][c]=j-i;
        }
    }

    return table;
}

void goodPre1(vector<int>& shift_table,vector<int>& memo_table,string pattern)
{
    int len,i,j;
    len=pattern.size();
    i=len;
    j=len+1;
    memo_table[i]=j;
    while(i>0){
        //?¬?????????????????????°????????????suffix??¨?????´????????¨????????????????????¨
        while(j<=len && pattern[i-1]!=pattern[j-1]){
            //shift_table[j]???0?????????????????????????¨????????????????????????????????????????
            if(shift_table[j]==0) shift_table[j]=j-i;
            //j???memo_table[j]????§????
            //
            j=memo_table[j];
        }
        i--;
        j--;
        memo_table[i]=j;
    }
}

void goodPre2(vector<int>& shift_table,vector<int>& memo_table,string pattern)
{
    int len,i,j;
    len=pattern.size();
    i=0;
    j=memo_table[0]; //prefix??¨suffix????????§?????´????????????index
    while(i<=len){
        if(shift_table[i]==0) shift_table[i]=j;
        //i==j??????????¬???????i>j????????£?????????????????????
        //j???????¬??????????prefix??¨suffix????????´????????????index???
        //????????????????????´???????????´???len???????¨?????????????
        //???????????????memo_table[j]??????
        //???j..len-1?????¨???????????????Pre1????????¨???????????¨?????????????????????
        if(i==j) j=memo_table[j];
        i++;
    }
}

vector<int> makeGoodSuffixTable(string pattern)
{
    vector<int> shift_table(pattern.size() + 1);
    vector<int> memo_table(pattern.size() + 1);
    goodPre1(shift_table, memo_table, pattern);
    goodPre2(shift_table, memo_table, pattern);
    return shift_table;
}

vector<int> bm(string text,string pattern)
{
    vector<int> matches;

    vector< vector<int> > bad_table;
    bad_table = makeBadCTable(pattern);
    vector<int> good_table=makeGoodSuffixTable(pattern);

    int ti,pi,tlen,plen;
    tlen=text.size();
    plen=pattern.size();

    ti=0; pi=plen-1;
    int goal=0;
    while(ti+plen<=tlen){
        if(pattern[pi]==text[ti+pi]){
            if(pi==goal){
                matches.push_back(ti);
                //goal=0;
                //ti++;
                ti=ti+good_table[0];
                goal=plen-good_table[0];
                pi=plen-1;
            }else{
                pi--;
            }
        }else{
            char bad_c=text[ti+pi];
            int bad_shift=bad_table[pi][bad_c];
            if(bad_shift<0) bad_shift=pi+1;

            //??¬????????????
           // if(good_table[pi+1]==pi+1 && pi+1<plen){
           //     goal=plen-pi-1;
           // }else{
           //     goal=0;
           // }
            goal=0;
            
            //printf("ti:%d,pi:%d,bad_shift:%d,good_shift:%d\n",ti,pi,bad_shift,good_table[pi+1]);
            ti=ti+max(bad_shift,good_table[pi+1]);
            pi=plen-1;
        }
    }
    return matches;
}

int main()
{
    string T,P;
    getline(cin,T);
    getline(cin,P);
    vector<int> matches = bm(T,P);
    for(auto item:matches){
        printf("%d\n",item);
    }
}

Measured memory_bytes: 19796