KMP

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
/*
                  a b b a a a a b a b a b a a
         next数组 0 1 1 1 2 2 2 2 3 2 3 2 3 2
   优化后的next数组0 1 1 0 2 2 2 1 3 1 3 1 3 2
*/
const int maxn=1e5+10;
int nextl[maxn];
void get_next(string s){              //字符数组从1开始
    nextl[1]=0;nextl[2]=1;
        int len=s.size();
    for(int i=3,j;i<=len;i++){
        j=i-1;
        while(nextl[j]&&s[i-1-1]!=s[nextl[j]-1]){
            j=nextl[j];
        }
        nextl[i]=nextl[j]+1;
    }
}
void nextcil(string s){           //next 数组优化
        int len=s.size();
    for(int i=3;i<=len;i++){
        if(s[i-1]==s[nextl[i]-1])nextl[i]=nextl[nextl[i]];
    }
}
int kmp_str(string s,string T){   //T在s中第一次出现位置，无匹配返回-1
    int lens=s.size(),lent=T.size(),i=1,j=1;
    while(i<=lens&&j<=lent){
        if(!j||s[i-1]==T[j-1])i++,j++;
        else j=nextl[j];
    }
    if(j>lent)return i-j+1;
    return -1;
}
int main(){
    int t;cin>>t;
    while(t--){
        string s,q;
        cin>>s>>q;
        //gets(s);
        //gets(T);
        int len=s.size(),kmp1,kmp2;
        kmp_get_next(s);
        kmp_bet_next(s);
        kmp2=kmp_str(s,q);


        if(kmp2!=-1)cout<<"YES\n";else cout<<"NO\n";

    }
}