☰

最も長い反復部分文字列を見つける方法は？ [閉鎖]

tag-icon • tag-icon text-processing
最も長い反復部分文字列を見つける方法は？ [閉鎖]

Ubuntuで次の問題を解決する方法を知っている人はいますか？テキストファイルに文字列があります。最も長い部分文字列を見つける方法S~へSそれ自体は元の文字列の部分文字列にリンクされていますか？

たとえば、元の文字列がある場合、hfhfggccaggccagccafff出力は必要ですggcca。しかし、元の文字列の長さが約700,000文字であれば、どのようなプログラムやスクリプトが機能しますか？

私の努力は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非常に長い行でこれをテストしていませんが、（および）への入力は「テキストファイル」に制限され、「テキストファイル」はPOSIXが「at」として定義するgrep最大文字行を持つファイルであることがわかりました。LINE_MAX「最小」2048（Ubuntuの実際の値でもあります）。修飾子に使用される数には制限があります\{n\}。

関連情報