网站开发所需要的的环境,国家高新技术企业所得税税率,东莞企业高端网站建设,怎么查找网站的根目录来源#xff1a;牛客网#xff1a;
题目描述 牛牛还是很喜欢字符串puleyaknoi。 牛牛有T个超长超长的字符串#xff0c;不过这次他更懒了#xff0c;他希望直接在字符串中看见他喜欢的字符串。 如果一个子串中含有一个子序列是”puleyaknoi“#xff0c;那么…来源牛客网
题目描述 牛牛还是很喜欢字符串puleyaknoi。 牛牛有T个超长超长的字符串不过这次他更懒了他希望直接在字符串中看见他喜欢的字符串。 如果一个子串中含有一个子序列是”puleyaknoi“那么他就把这个子串称作好的子串。 牛牛是个懒人他不喜欢看太长的子串那样他会觉着眼镜很累。 你能帮他求出对于每个字符串最短的好的子串的长度是多少吗 如果没有请输出-1。 输入描述: 第一行一个T表示数据组数 接下来T行每行一个字符串保证字符串只含小写字母 输出描述: 共T行每行一个答案 示例1 输入 复制
3
sxpuleyaaknoip
pionkaayelupxs
yydspwuwlwewywawkwnwowiw输出 复制
11
-1
19备注: T10,字符串长度不超过10^5T≤10,字符串长度不超过10 5
题解
我一开始想的是在A题的基础上改A题是打乱顺序B题是找子串子串其实就是相对位置已经固定只是不一定靠着而已 我用A题作为模板改完后意识到复杂度过高肯定会TEL决定换一个方式 用序列自动机来做序列自动机专门来求子串问题典型的空间换时间 记录每个位置往后最近的字母的位置 然后从p才是出发匹配我们所需要的子串
int nxt[maxn][30];
int now[30];
char s[maxn];
void init()
{//序列自动机预处理memset(now, -1, sizeof now); //mow_i表示第i个字母在原串中从后向前最晚出现的位置int len strlen(s);--len;for(int i len; ~i; --i) //处理每一个字符{for(int j 0; j 26; j) //找出第i个字符后面的26个字母最早出现的字符的位置nxt[i][j] now[j];now[s[i] - a] i; //用当前字符更新当前字符在原串中从后向前最晚出现的位置}
}
查找时这样 now nxt[now][mark[pos] - ‘a’]; 从前向后找
代码
#includebits/stdc.h
const int INF1e89;
using namespace std;
string spuleyaknoi;
const int maxn1e59;
int nxt[100009][37];
int now[maxn];
int main()
{int t;cint;while(t--){string a;cina;for (int i 0; i 26; i) nxt[a.length()][i] -1;for(int ia.length()-1;i0;i--){for(int j0;j26;j)nxt[i][j]nxt[i1][j];int wa[i]-a;nxt[i][w]i;} int annINF;for(int i0;ia.length();i){if(a[i]s[0]){int timenxt[i][s[0]-a];int pos1;while(time!-1pos10){timenxt[time][s[pos]-a];}if(time!-1pos10)annmin(ann,time-i1);}}if(annINF)cout-1endl;else coutannendl; }return 0;
}
