在 Python 中查找最长的子字符串,该子字符串既是前缀,又是后缀,并且也存在于字符串中

pythonserver side programmingprogramming更新于 2025/9/30 10:20:17

假设我们有一个给定的字符串,我们必须找到最大的子字符串,该子字符串既是前缀,又是后缀,又是该给定字符串的子字符串。如果没有这样的子字符串,则返回 -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

相关文章


有用资源