查找Python中最长的子字符串，该子字符串既是前缀又是后缀，并且也出现在字符串中

假设我们有一个给定的字符串，我们需要找到最大的子字符串，它是该给定字符串的前缀、后缀和子字符串。如果没有这样的子字符串，则返回-1。

因此，如果输入类似于“languagepythonlanguageinterestinglanguage”，则输出将是“language”。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数`get_lps()`。这将接收字符串作为参数。

  • n := 字符串的大小

  • long_pref_suff := 一个大小为n的数组，并填充为0

  • size := 0，long_pref_suff[0] := 0，i := 1

  • 当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]，则

      • 返回string的子字符串（从索引0到long_pref_suff[i]）

  • 如果long_pref_suff[long_pref_suff[n - 1] - 1]等于0，则

    • 返回-1

  • 否则，

    • 返回string的子字符串（从索引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

更新于：2020年8月20日

809 次查看

开启你的职业生涯

完成课程获得认证

开始学习
广告