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