拼凑

题目描述

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

牛牛有T个超长超长的字符串，不过这次他更懒了，他希望直接在字符串中看见他喜欢的字符串。

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

牛牛是个懒人，他不喜欢看太长的子串，那样他会觉着眼镜很累。

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

如果没有，请输出-1。

输入描述:

第一行一个T表示数据组数接下来T行每行一个字符串（保证字符串只含小写字母）

输出描述:

共T行每行一个答案

示例1

输入

复制

3
sxpuleyaaknoip
pionkaayelupxs
yydspwuwlwewywawkwnwowiw

输出

复制

11
-1
19

备注:

T≤10,字符串长度不超过1e5

区分子串和子序列

给定 "pwwkew" ，

子串是pww,wwk等很多个子串 是连在一起的

子序列是 pwk,pke等很多个子序列 ，但是子序列中的字符在字符串中不一定是连在一起的。

题目分析：题目要找的是子序列，也就是在一串字符串中连续找出对应子串的字符，可以不相邻，但是一定要连续,题目的正解应该是序列自动机，但是这个题目也可以用模拟，具体看代码

方法一：模拟

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char c[maxn];
string s = "puleyaknoi";

int main()
{
    int n;
    scanf("%d", &n);
    getchar();
    for (int i = 1; i <= n; ++i)
    {
        int ans = -1;
        scanf("%s", c);
        int lc = strlen(c);
        for (int i = 0; i < lc; ++i)
        {
            if (c[i] == 'p') //只有开头是p字符才继续找
            {
                int k = 1; //找打的个数
                for (int j = i + 1; j < lc; ++j)
                {
                    if (c[j] == s[k])
                        ++k;
                    if (k == s.size()) //因为我们定义k是找到对应字符的个数，所以这里判断是s.size()
                    {
                        if (ans == -1) //第一次找到
                            ans = j - i + 1;
                        else
                            ans = min(ans, j - i + 1); //如果后续有更小的就更新一下
                        break;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

方法二：序列自动机

ps：序列自动机比较冷门？（听说）稍微有点难以理解，就是记录一下第i个位置后第一个j出现的位置，有点跳跃性的查找

#include <bits/stdc++.h>
const int inf = 1e8 + 9;
using namespace std;
string s = "puleyaknoi";
const int maxn = 1e5 + 9;
int nxt[100009][37];
int now[maxn];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string a;
        cin >> a;
        for (int i = 0; i < 26; i++)
            nxt[a.length()][i] = -1;
        for (int i = a.length() - 1; i >= 0; i--)
        {
            for (int j = 0; j < 26; j++)
                nxt[i][j] = nxt[i + 1][j];
            nxt[i][a[i] - 'a'] = i;
        }
        int ans = inf;
        for (int i = 0; i < a.length(); i++)
        {
            if (a[i] == s[0])
            {
                int time = nxt[i][s[0] - 'a'];
                int pos = 1;
                while (time != -1 && pos < 10)
                    time = nxt[time][s[pos++] - 'a'];
                if (time != -1 && pos == 10)
                    ans = min(ans, time - i + 1);
            }
        }
        if (ans == inf)
            puts("-1");
        else
            printf("%d\n", ans);
    }
    return 0;
}