0

重複の可能性:
文字列内で最も長い反復シーケンスを見つける

私は問題に取り組んでおり、最も繰り返されるパターンを見つける必要があります。

シンプルさと利便性のために、次の文字列を検討してください。

What is Lorem Ipsum?
Lorem Ipsum is simply dummy text of the printing and typesetting industry.
Lorem Ipsum has been the industry's standard dummy text ever since the 1500s...

最も繰り返されるシーケンス (たとえば、文字列の長さが 3 文字を超えることを最初に考慮する) は "Lorem Ipsum" です。「ロレム」と「イプサム」ももちろん同じ回数繰り返しますが、同じ回数繰り返す場合は短い弦よりも長い弦が優先されます。

できればPythonで、このパターンを効率的に見つけることができるアルゴリズムはどのようなものですか?

4

1 に答える 1

0

@fraxel が示したように、問題をもう少し詳しく説明する必要がありますが、これはせいぜい動的プログラミング (http://en.wikipedia.org/wiki/Dynamic_programming) の問題のように思えます。ただし、さらに指定しないと、必要なアルゴリズムの種類を知ることはできません。たとえば、パターンの定義の定式化における別の不確実性です。パターンは単純な文字列ですか? または、「ababa」は、正規表現またはグロブ パターン「a*a*a」に一致するという点で、「acaca」と同じパターンと見なされます。

于 2012-06-19T20:57:31.600 に答える