题目链接

https://ac.nowcoder.com/acm/contest/7509/B

解题思路

我的思路：
pos记录属于puleyaknoi中字符的位置，pos_of_p_in_pos记录p在pos中的位置。
从pos_of_p_in_pos数组的最后一个p开始往后找字符串，按顺序puleyaknoi中的字符，若能找全，刷新ans。
大佬思路：
核心是用v[i]表示puleyaknoi中所有第i个字符的位置，是从小到大排序的，因为是从小到大push的。
枚举p的位置，作为区间左端点，字符串最右端作为右端点，check参数为i和二分的区间长度。
长度可行刷新ans，同时缩短区间。

我的AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
char s[15]=".puleyaknoi";
int FindIDX(char ch){
    for(int i=1;i<=10;i++) if(ch==s[i]) return i;
    return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string  str;
        cin>>str;
        int len=str.length();
        str='.'+str;

        int pos[N],pos_of_p_in_pos[N];
        int num=0,nump=0;
        for(int i=1;i<=len;i++){
            int tmp=FindIDX(str[i]);
            if(tmp) pos[++num]=i;
            if(tmp==1) pos_of_p_in_pos[++nump]=num;
        }

        int ans=N;
        for(int i=nump;i>=1;i--){
            int k=1,j=pos_of_p_in_pos[i];
            for(;j<=num&&k<=10;j++){
                if(str[pos[j]]==s[k]) k++;
            }
            if(k==11) ans=min(ans,pos[j-1]-pos[pos_of_p_in_pos[i]]+1);
        }
        if(ans>len) cout<<-1<<endl;
        else cout<<ans<<endl;
    /*    
        cout<<"________________________________"<<endl;
        for(int i=1;i<=num;i++) cout<<pos[i]<<' ';
        cout<<endl;
        for(int i=1;i<=nump;i++) cout<<pos_of_p_in_pos[i]<<' ';
        cout<<endl;
        cout<<"________________________________"<<endl;
    */
    }
}

大佬AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
vector<int> v[N];
int IS(char ch){
    if(ch=='p') return 1;
    else if(ch=='u') return 2;
    else if(ch=='l') return 3;
    else if(ch=='e') return 4;
    else if(ch=='y') return 5;
    else if(ch=='a') return 6;
    else if(ch=='k') return 7;
    else if(ch=='n') return 8;
    else if(ch=='o') return 9;
    else if(ch=='i') return 10;
    return 0;
}
bool check(int p,int len){
    int tmp=p;
    for(int i=2;i<=10;i++){
        p=*lower_bound(v[i].begin(),v[i].end(),p);//不可以用upper_bound，因为假如p=N，那么p在下一次循环中的upper_bound中会被赋值成v中未知域的随机值。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
vector<int> v[N];
int IS(char ch){
    if(ch=='p') return 1;
    else if(ch=='u') return 2;
    else if(ch=='l') return 3;
    else if(ch=='e') return 4;
    else if(ch=='y') return 5;
    else if(ch=='a') return 6;
    else if(ch=='k') return 7;
    else if(ch=='n') return 8;
    else if(ch=='o') return 9;
    else if(ch=='i') return 10;
    return 0;
}
int GetLenth(int p,int len){
    int tmp=p;
    for(int i=2;i<=10;i++){
        p=*lower_bound(v[i].begin(),v[i].end(),p);
    } 
    if(p>tmp+len-1) return 0;
    else return p-tmp+1; 
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string str;
        for(int i=0;i<=10;i++) v[i].clear();
        cin>>str;
        int len=str.length();
        str='.'+str;
        for(int i=1;i<=len;i++){
            v[IS(str[i])].push_back(i);
        }
        for(int i=1;i<=10;i++) v[i].push_back(N);

        int ans=N;
        for(int i=1;i<=len;i++){
            if(str[i]=='p'){
                int tmp=GetLenth(i,len-i+1);
                if(tmp) ans=min(ans,tmp);
            }
        }
        if(ans>=N) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}
    } 
    if(p>tmp+len-1) return false;
    else return true; 
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string str;
        for(int i=0;i<=10;i++) v[i].clear();
        cin>>str;
        int len=str.length();
        str='.'+str;
        for(int i=1;i<=len;i++){
            v[IS(str[i])].push_back(i);
        }
        for(int i=1;i<=10;i++) v[i].push_back(N);

        int ans=N;
        for(int i=1;i<=len;i++){
            if(str[i]=='p'){
                int l=10,r=len-i+1;
                while(l<=r){//二分
                    int m=(l+r)>>1;
                    if(check(i,m)) r=m-1,ans=min(ans,m);
                    else l=m+1;
                }
            }
        }
        if(ans>=N) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}

改编大佬代码后

我发现其实二分操作是多余的，只要用容器存好，利用lower_bound函数求出的就是最短的。
GetLenth参数为左端点为i，右端点始终为字符串右端点。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
vector<int> v[N];
int IS(char ch){
    if(ch=='p') return 1;
    else if(ch=='u') return 2;
    else if(ch=='l') return 3;
    else if(ch=='e') return 4;
    else if(ch=='y') return 5;
    else if(ch=='a') return 6;
    else if(ch=='k') return 7;
    else if(ch=='n') return 8;
    else if(ch=='o') return 9;
    else if(ch=='i') return 10;
    return 0;
}
int GetLenth(int l,int r){
    int tmp=l;
    for(int i=2;i<=10;i++){
        l=*lower_bound(v[i].begin(),v[i].end(),l);
    } 
    if(l>r) return 0;
    else return l-tmp+1; 
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string str;
        for(int i=0;i<=10;i++) v[i].clear();
        cin>>str;
        int len=str.length();
        str='.'+str;
        for(int i=1;i<=len;i++){
            v[IS(str[i])].push_back(i);
        }
        for(int i=1;i<=10;i++) v[i].push_back(N);

        int ans=N;
        for(int i=1;i<=len;i++){
            if(str[i]=='p' && len-i+1>=10){
                int tmp=GetLenth(i,len);
                if(tmp) ans=min(ans,tmp);
            }
        }
        if(ans>=N) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}