Как найти самую длинную повторяющуюся подстроку?
Частичный ответ на непроверенную идею.
Открывайте файлы по имени, exec, у вас все еще есть дескрипторы файлов, так что mmapих.
С GNU grep:
echo hfhfggccaggccagccafff |
grep -Po '(.*)\K\1' | awk 'length > l {l=length;s=$0} END{print s}'
ggcca
Конечно, это не приведет к перекрытию последовательностей.
$ 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, если он это делает (, переходя к концу сценария с помощью t, если замена сделана предыдущим s///. ] команда ).
Для заданных данных генерируется следующий 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(иgrep)ограничен «текстовыми файлами» и что «текстовый файл» — это файл, строки которого не превышают LINE_MAXсимволов, которые POSIX определяет как «не менее» 2048 (, что также является его фактическим значением в Ubuntu ). Кроме того, существуют ограничения на количество, используемое в модификаторе \{n\}.