問題タブ [subsequence]

たとえば、シーケンスを見てみましょう

繰り返し文字を含むすべてのサブシーケンスに正規表現を一致させたい。つまり、サブシーケンスの合計数は 3 ではなく 5 にする必要があります。

説明:

文字を数えましょう。私たちのシーケンスは次のようになります

すべてのサブシーケンスは次のとおりです。

正規表現でそれを行うことはできますか? 私は現在 Java でプログラミングを行っており、Java でアルゴリズムを開発できることはわかっていますが、今のところは避けたいと思います。

カテゴリ変数「世代」があります。を使用して各世代の最頻サブシーケンスを計算したいのですTraMineRが、特定のコホートが必要であることを指定する方法がわかりません。私が知っているすべての可能な解決策を試しましたが、これまでのところ何もうまくいきませんでした。これは私が指定できないコードです:

次のようなリストを指定するアルゴリズムを探しています。

[1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 1]

指定された値のすべてのサブシーケンスを検索して返すことができます。たとえば、値 1 が指定された場合、関数は を返し[[1, 1], [1, 1], [1, 1, 1, 1], [1]]ます。

これは、配列のすべてのサブシーケンスを合計したり、特定の文字列のすべてのサブシーケンスを見つけたりするような問題に似ていると思いますが、アルゴリズムは私の得意分野ではありませんでした。答えは、擬似コードまたは言語に依存しない場合があります。よろしければ、ソリューションの複雑さを説明していただけますか?

それが役立つ場合、これが何のために必要かを説明できます。欲しい方はコメントください。

文字列を回文に変換するために必要な挿入の最小数を見つける必要があります。注: 挿入は、任意の場所、末尾、または内部で発生する可能性があります。最後だけだったら、ここで質問があります。

O(N**2)したがって、これは次の簡単なトリックで時間内に実行できることがわかりました。

1. 文字列を s1 とします。それを逆にします。s2 とする．長さは としlます。
2. 次に、s1 と s2 の最長共通部分列を見つけます。その長さを とするx。
3. 答えはl-xです。

たとえば、 としますs1 = abcda。したがってs2 = adcba。長さは 5 です。最長の共通サブシーケンスはaba長さ 3 です。したがって、挿入の最小数は であり5-3 = 2、これが実際の答えであり、結果の文字列は -です。adcbcda

ただし、その背後にあるロジックは理解できません。なぜそれが機能するのか、誰かが私に説明できますか?

そして、これに対するO(N)解決策はありますか？