プレフィックス、サフィックスであり、Pythonの文字列内にも存在する最長のサブ文字列を検索します

指定された文字列があるとすると、その指定された文字列のプレフィックス、サフィックス、およびサブ文字列である最大のサブ文字列を見つける必要があります。そのような部分文字列がない場合は、-1を返します。

したがって、入力が「languagepythonlanguageinterestinglanguage」のような場合、出力は「language」になります

これを解決するには、次の手順に従います-

• 関数get_lps（）を定義します。これには文字列が必要です

• n：=文字列のサイズ

• long_pref_suff：=サイズnの配列で、0で埋めます

• サイズ：=0、long_pref_suff [0]：=0、i：=1

• i

  • string[i]がstring[size]と同じ場合、

    • サイズ：=サイズ+ 1

    • long_pref_suff [i]：=サイズ

    • i：=i + 1

  • それ以外の場合

    • サイズが0と同じでない場合は、

      • サイズ：=long_pref_suff[サイズ-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