Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

접두사, 접미사이며 Python의 문자열 내부에도 존재하는 가장 긴 하위 문자열 찾기


주어진 문자열이 있다고 가정하면 해당 문자열의 접두사, 접미사 및 하위 문자열인 가장 큰 하위 문자열을 찾아야 합니다. 그러한 부분 문자열이 없으면 -1을 반환합니다.

따라서 입력이 "languagepythonlanguageinterestinglanguage"와 같으면 출력은 "언어"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • get_lps() 함수를 정의합니다. 문자열이 필요합니다.

  • n :=문자열의 크기

  • long_pref_suff :=크기가 n인 배열, 0으로 채움

  • 크기 :=0, long_pref_suff[0] :=0, 나는 :=1

  • i

    • string[i]가 string[size]와 같으면

      • 크기 :=크기 + 1

      • long_pref_suff[i] :=크기

      • 나는 :=나는 + 1

    • 그렇지 않으면

      • 크기가 0과 같지 않으면

        • 크기 :=long_pref_suff[크기 - 1]

      • 그렇지 않으면

        • long_pref_suff[i] :=0

        • 나는 :=나는 + 1

  • long_pref_suff 반환

  • 기본 방법에서 다음을 수행하십시오 -

  • long_pref_suff :=get_lps(문자열)

  • 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