KMP

#include <iostream>
#include <string>
using namespace std;


void getNext(int next[],string s){
    int j=0;
    next[0]=0;
    for(int i=1;i<s.size();i++){
        while( j>0 && s[j]!=s[i]){
            j=next[j-1];
            //next[i]=j;
        }
        if(s[j]==s[i]){
            j++;
            next[i]=j;
        }
    }
}

int main(){
    string s;
    getline(cin,s);
    int next[s.size()];
    if(s.size()==0) return 0;
    getNext(next,s);
    int j=0;
    string S;
    getline(cin,S);
    for(int i=0;i<S.size();i++){
        while(j>0&&S[i]!=s[j]) j=next[j-1];
        if(S[i]==s[j]) j++;

    }
    if(j==s.size()) return 1;

    return -1;
}