#include<iotream>
#include<vector>
using namespace std;
vector<int>LPS(string){
    int i=1;j=0,len=patte.length();
    vector<int>lps(len,0);
    while(i<len){
        if(patte[i]==patte[j]){
            j++;
            lps[i]=j;
            i++;
        }
        else{
            if(j!=0)
               j=lps[j-1];
            else{
               lps[i]=0;
               i++;
            }
        }
    }
    return lps;
}

int main(){
    string text,patte;
    int i=0,j=0,len1,len2;
    getline(cin,text);
    cin>>patte;
    vector<int>lps=LPS(patte);
    len1=text.length();
    len2=patte.length();
    while(i<len1){
        if(text[i]==patte[j]){
            i++;
            j++;
        }
        if(j==len2){
            cout<<"Found pattern at index "<<i-j<<endl;
            j=lps[j-1];
        }
        else if(i<len1 && text[i]!=patte[j]){
            if(j!=0)
                j=lps[j-1];
            else
                i++;
        }
    }
    return 0;
}