☰

가장 긴 반복 부분 문자열을 찾는 방법은 무엇입니까? [폐쇄]

tag-icon • tag-icon text-processing
가장 긴 반복 부분 문자열을 찾는 방법은 무엇입니까? [폐쇄]

Ubuntu에서 다음 문제를 해결하는 방법을 아는 사람이 있습니까? 텍스트 파일에 문자열이 있습니다. 가장 긴 부분 문자열을 찾는 방법에스~에에스자체가 원래 문자열의 하위 문자열로 연결됩니까?

예를 들어 원래 문자열이 이면 hfhfggccaggccagccafff출력은 이어야 합니다 ggcca. 하지만 원래 문자열의 길이가 약 700,000자라면 어떤 종류의 프로그램이나 스크립트가 작동할까요?

내 노력은 파이썬 스크립트입니다

import re

s = 'hfhfggccaggccagccafff'
def find(s):
    r=max(re.findall(r'((\w+?)\2+)', s), key=lambda t: len(t[0]))

    return r

print(find(s))

답변1

GNU grep을 사용하십시오:

echo hfhfggccaggccagccafff |
grep -Po '(.*)\K\1' | awk 'length > l {l=length;s=$0} END{print s}'

ggcca

물론 이로 인해 시퀀스가 ​​겹치지는 않습니다.

답변2

$ sed -n -f <( awk '{ for (i = int(length/2) + 1; i > 0; --i) printf "s/.*\\(.\\{%d\\}\\)\\1.*/\\1/p;t\n", i }' file ) file
gccag

awk이는 많은 명령문을 생성 하는 데 사용됩니다 sed. 각 문은 특정 길이의 반복되는 하위 문자열을 찾기 위해 일치 항목을 시도하고, 그렇게 하는 경우 스크립트를 종료합니다(또는 이전 명령이 대체를 수행한 경우 sed스크립트 끝으로 분기 ).ts///

지정된 데이터에 대해 sed다음 스크립트가 생성됩니다.

s/.*\(.\{11\}\)\1.*/\1/p;t
s/.*\(.\{10\}\)\1.*/\1/p;t
s/.*\(.\{9\}\)\1.*/\1/p;t
s/.*\(.\{8\}\)\1.*/\1/p;t
s/.*\(.\{7\}\)\1.*/\1/p;t
s/.*\(.\{6\}\)\1.*/\1/p;t
s/.*\(.\{5\}\)\1.*/\1/p;t
s/.*\(.\{4\}\)\1.*/\1/p;t
s/.*\(.\{3\}\)\1.*/\1/p;t
s/.*\(.\{2\}\)\1.*/\1/p;t
s/.*\(.\{1\}\)\1.*/\1/p;t

일치하는 항목이 발견될 때까지 반복의 길이가 내림차순으로 테스트됩니다.

sed매우 긴 줄에서 이것을 테스트하지는 않았지만 (및 )에 대한 입력은 "텍스트 파일"로 제한되고 "텍스트 파일"은 POSIX가 "at"로 정의하는 grep최대 문자 줄이 있는 파일이라는 것을 알았습니다. LINE_MAX최소" 2048(우분투에서의 실제 값이기도 합니다). 또한 수정자에 사용되는 수에는 제한이 있습니다 \{n\}.

관련 정보