字符串的问题

[编程题]字符串的问题

热度指数：920 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个字符串让你找到这个字符串 S 里面的子串T 这个子串 T 必须满足即使这个串的前缀也是这个
串的后缀并且在字符串中也出现过一次的(提示要求满足前后缀的同时也要在字符串中出现一次只是前后缀可不行输出最长满足要求字符串)

输入描述:

给出一个字符串 长度 1 到 1e6  全部是小写字母

输出描述:

如果找的到就输出这个子串T 如果不行就输出 Just a legend

示例1

输入

fixprefixsuffix

输出

fix

示例2

输入

abcdabc

输出

Just a legend

算法知识视频讲解

苟且的狮子

发表于 2020-08-28 23:13:09

kmp 题意：分析：我们看着一题，我们仔细想想。首先如果没有要求中间子串的话，就很简单了。我们直接输出前后缀相等的就好了。无论是 kmp 还是暴力都是线性时间。但是麻烦就在于中间要有字串。那我们想想，如何判断中间有没有子串呢？假设，next[n] = k 意味着s0,s1,s 展开全文

威风镰鼬

发表于 2021-08-29 10:45:18

思路首先如果要求最大前缀的话，我们用Kmp就能线性求出来。题目要求中间也有一个和最大前缀一样的东西，久相对增加了点难度。那我们失配数组每个值出现的次数，如果最终nxt[len]（即整个串的最长后缀）出现过不止一次，就可以输出答案了。但是这样写还需要考虑点细节。比如aaaa的情况，在中间出现的并不能展开全文

狂点技能树

发表于 2021-05-11 21:14:31

题解思路：参考楼下大佬的思路：是否有和最后一个next[]相同的next值在数组中间出现，若存在最后一个next就是答案。否则，next[最后一个next]才是解（当然，特判解不存在）。这里重点贴一下代码，其中未注释代码为从 0 开始的 next 数组求解，注释的代码则是从 1 开始的 next 展开全文