2

重複の可能性:
Square Subsequence

私は、interviewstreet.com で「 Square Subsequences 」の問題を解決しようとしています。

同じ文字列の 2 つのコピーを連結して得られる文字列は、正方形文字列と呼ばれます。たとえば、「abab」、「aa」は正方形の文字列ですが、「aaa」、「abba」はそうではありません。

文字列が与えられたとき、その文字列の何個のサブシーケンスが正方形の文字列ですか?

DP ソリューションを試してみましたが、この制約を回避することは不可能のようです: S will have at most 200 lowercase characters (a-z).

私の知る限り、長さのリストのすべてのサブシーケンスを見つけることは です。これnは、たとえば 30 を超えるとO(2^n)すぐに実行できなくなります。n

n200の場合、すべての解を体系的にチェックすることは本当に可能ですか? どのようにアプローチすればよいですか？

4

2 に答える 2

0

線形時間でプレフィックス長の配列を生成できる多くのアルゴリズム (たとえばZ-algorithm ) があります。つまり、位置 i ごとに、位置 i から読み取れる最長の接頭辞を示します (もちろん、i = 0 までの最長の接頭辞は n です)。

ここで、先頭から始まる正方形の文字列がある場合、この接頭辞の長さの配列には位置 k があり、最長の長さが >=k であることに注意してください。したがって、線形時間でそれらの数をもう一度数えることができます。

次に、文字列の最初の文字を削除して、同じことを行います。これの全体の複雑さは O(n^2) になります。

于 2012-06-28T09:52:53.143 に答える