(二分+hash)Obtain The String

03
五月
2021

Obtain The String

在这里插入图片描述
在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
char a[N],b[N];
vector<int> p[50];
int erfen(int u,int t){
    int l=0,r=p[u].size()-1;
    while(l<=r){
        int mid=l+r>>1;
        if(p[u][mid]<t)
            l=mid+1;
        else
            r=mid-1;

    }
    return l;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>a>>b;
        int lena=strlen(a);
        int lenb=strlen(b);
        for(int i=0;i<50;i++)
            p[i].clear();
        for(int i=0;i<lena;i++)
            p[a[i]-'a'].push_back(i);
        int ans=1,temp=0;//temp可取
        for(int i=0;i<lenb;i++){
            if(!p[b[i]-'a'].size()){
                ans=-1;
                break;
            }
            int er=erfen(b[i]-'a',temp);
            if(er==p[b[i]-'a'].size()){
                ans++;
                temp=p[b[i]-'a'][erfen(b[i]-'a',0)]+1;
            }else{
                temp=p[b[i]-'a'][er]+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员