拼凑

题目

牛牛还是很喜欢字符串 "puleyaknoi"。

牛牛有 T 个超长超长的字符串，他希望直接在字符串中看见他喜欢的字符串。

如果一个子串中含有一个子序列是 "puleyaknoi"，那么他就把这个子串称作好的子串。

求出对于每个字符串，最短的好的子串的长度是多少？

如果没有，请输出-1。

T≤10，字符串长度不超过 10⁵。

解题思路

遍历字符串 s，遇到字符 'p' 时，遍历 s 后面的字符，如果能组成好的子串，记录子串的长度并更新。

C++代码

#include<iostream>
using namespace std;

string str = "puleyaknoi";

int main(){
    int T;
    string s;
    cin >> T;
    while(T--){
        cin >> s;
        int ans = -1;
        int i = 0;
        for(int i=0; i<s.size(); ++i){
            if(s[i]=='p'){
                int k = 1;
                for(int j=i+1; j<s.size(); ++j){
                    if(s[j]==str[k])
                        ++k;
                    if(k==str.size()){
                        if(ans == -1) ans = j-i+1;
                        else ans = min(ans, j-i+1);
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}