入力として、長さ 3 の n+2 個の連続した部分文字列のリストがあります。私の目標は、長さ 2 のすべての連続した部分文字列が、与えられた入力リストとまったく同じになるような、長さ n の文字列が存在するかどうかを調べることです。
この問題を効率的に解決するにはどうすればよいですか (たとえば、長さ 4000 の文字列の場合)。
マトリックスチェーン乗算に使用されるものと同様の DP アプローチを試しましたが、うまくいきませんでした。
この問題を、部分文字列が頂点であり、部分文字列を長さ 4 の部分文字列に結合できる場合 (例: abc と bcd abcd に結合できるように接続されています)。このグラフでオイラー パスを見つけようとすると、問題が解決しますか? それとも、私はこれらすべてについて完全に間違っていますか?