☰

如何找到最长的重复子串？

tag-icon • tag-icon text-processing
如何找到最长的重复子串？

有谁知道如何在 Ubuntu 上解决以下问题吗？我在文本文件中有一个字符串。如何找到最长的子串S其中S本身连接起来是原始字符串上的子字符串？

例如，如果原始字符串是hfhfggccaggccagccafff，则输出应该是ggcca。但是，如果原始字符串大约有 700000 个字符长，什么样的程序或脚本可以工作呢？

我的努力是一个Python脚本

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我没有在很长的行上对此进行测试，但我注意到(and )的输入grep仅限于“文本文件”，并且“文本文件”是行最多为字符的文件LINE_MAX，POSIX 将其定义为“至少”2048（这也是它在 Ubuntu 上的实际值）。此外，修饰符中使用的数量也有限制\{n\}。

相关内容