サフィックス ツリーを使用して、(部分文字列ではなく) 個別の部分列の数を数えることはできますか?
定義: 文字列のサブシーケンスは、残りの文字の相対位置を乱すことなく文字の一部を削除することによって、元の文字列から形成される新しい文字列です。(つまり、「ACE」は「ABCDE」のサブシーケンスですが、「AEC」はそうではありません)。
では、String S = "rabbbit"、サブシーケンスのパターン P = "rabbit" が与えられた場合、サフィックス ツリーを使用して、S 内の P の異なるサブシーケンスの数を見つけることができますか?
手動検査から 3 を返す必要があります。
「ウサギ」の接尾辞ツリーを描画してこの問題を解決することで、誰かがこのトピックについて良い教育をしてくれると本当にありがたいです。
注 - この問題は DP などの他の手法で解決できますが、接尾辞ツリーを使用して解決できるかどうかに興味があります。ありがとう！