在 Python 中查找最长的子字符串,该子字符串既是前缀,又是后缀,并且也存在于字符串中
假设我们有一个给定的字符串,我们必须找到最大的子字符串,该子字符串既是前缀,又是后缀,又是该给定字符串的子字符串。如果没有这样的子字符串,则返回 -1。
因此,如果输入为"languagepythonlanguageinterestinglanguage",则输出将为"language"
为了解决这个问题,我们将遵循以下步骤 −
定义一个函数 get_lps() 。这将采用字符串
n := 字符串的大小
long_pref_suff := 大小为 n 的数组,并用 0 填充
size := 0, long_pref_suff[0] := 0, i := 1
while i < n 非零,则执行
如果 string[i] 与 string[size] 相同,则
size := size + 1
long_pref_suff[i] := size
i := i + 1
否则,
如果 size 不等于 0,则
size := long_pref_suff[size - 1]
否则,
long_pref_suff[i] := 0
i := i + 1
返回 long_pref_suff
从主方法中,执行以下操作 −
long_pref_suff := get_lps(string)
n := 字符串的大小
如果 long_pref_suff[n - 1] 与 0 相同,则
返回 -1
对于范围为 0 到 n - 1 的 i,执行
如果 long_pref_suff[i]与 long_pref_suff[n - 1] 相同,则
返回字符串的子字符串[从索引 0 到 long_pref_suff[i]]
如果 long_pref_suff[long_pref_suff[n - 1] - 1] 与 0 相同,则
返回 -1
否则,
返回字符串的子字符串[从索引 0 到 long_pref_suff[long_pref_suff[n - 1] - 1]]
示例
让我们看看下面的实现以便更好地理解 −
def get_lps(string): n = len(string) long_pref_suff = [0 for i in range(n)] size = 0 long_pref_suff[0] = 0 i = 1 while (i < n): if (string[i] == string[size]): size += 1 long_pref_suff[i] = size i += 1 else: if (size != 0): size = long_pref_suff[size - 1] else: long_pref_suff[i] = 0 i += 1 return long_pref_suff def get_longest_substr(string): long_pref_suff = get_lps(string) n = len(string) if (long_pref_suff[n - 1] == 0): return -1 for i in range(0,n - 1): if (long_pref_suff[i] == long_pref_suff[n - 1]): return string[0:long_pref_suff[i]] if (long_pref_suff[long_pref_suff[n - 1] - 1] == 0): return -1 else: return string[0:long_pref_suff[long_pref_suff[n - 1] - 1]] string = "languagepythonlanguageinterestinglanguage" print(get_longest_substr(string))
输入
"languagepythonlanguageinterestinglanguage"
输出
language
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

