KMP

作者: 我好菜啊_ | 来源:发表于2018-06-09 09:08 被阅读0次
    #include <iostream>
    #include <string>
    #include <vector>
    #include <cstring>
    
    #define MAX 100005
    using namespace std;
    string strA,strB;
    int next[MAX];
    
    void initNext(string str)
    {
        next[0]=-1;
        int j=0,k=-1;
        while(j!=str.size()){
            while(k!=-1&&str[j]!=str[k])
                k=next[k];
            ++j;
            ++k;
            if(str[j]!=str[k])
                next[j]=k;
            else
                next[j]=next[k];
        }
    }
    
    int KMP(string s1,string s2)
    {
        int flag=0;
        int i=0,j=0;
        while(i!=s1.size()){
                while(j!=-1&&s1[i]!=s2[j])
                    j=next[j];
                ++i;
                ++j;
                if(j==s2.size()){
                    ++flag;
                    j=0;
                }
        }
        //cout<<flag<<endl;
        return flag;
    }
    
    void reverseStr(string &str)
    {
        int l=str.size();
        for(int i=0;i<str.size()/2;++i)
        {
            char c=str[i];
            str[i]=str[l-i-1];
            str[l-i-1]=c;
        }
    }
    int main()
    {
    
        int t;
        cin>>t;
        for(int i=0;i<t;++i){
            cin>>strA>>strB;
            if(strB=="0"){
                cout<<"Alice"<<endl;
            }else{
                memset(next,-1,sizeof(next));
                initNext(strB);
                if(KMP(strA,strB)>0){
                    cout<<"Alice"<<endl;
                }else{
                   reverseStr(strB);
                   if(strB[0]=='0'){
                    strB=strB.substr(1,strB.size()-1);
                   }
                   memset(next,-1,sizeof(next));
                   initNext(strB);
                   if(KMP(strA,strB)>0){
                    cout<<"Alice"<<endl;
                   }else{
                    cout<<"Bob"<<endl;
                   }
                }
    
            }
        }
        return 0;
    }
    
    

    相关文章

      网友评论

          本文标题:KMP

          本文链接:https://www.haomeiwen.com/subject/tbtteftx.html