c++ - XYZ と XZY の 2 つの文字列

Question

同じ長さの 2 つの文字列があります。そして、Y と Z が空でない XYZ と XZY として表現できるかどうかを確認する必要があります。

私の解決策は、両方の文字列の同じ最初の文字を「食べ」、残りの最長共通部分文字列を見つけることです。次に、最初の文字列の残りと 2 番目の文字列の残り (LCS なし) が等しいかどうかを確認します。問題は、このための O(N) メモリ複雑性アルゴリズムについて聞いたことですが、私が見つけたのは O(MN) だけです。私は記憶力が限られているので、それは私にとって重要です。

2 番目の解決策は、"(.*)(.+)(.+)\1\3\2" 正規表現を使用することですが、これは非常に貧弱な解決策です。

他のアイデアはありますか？

Answer 1

検証されていません。検討の材料です。

1. 2 番目の文字列を逆にして、最初の文字列に接続します (例: XYZY'Z'X')。（またはその逆）
2. size(X) <= len(XYZY'Z'X')/2 の場合、可能な限り長い X == X' を見つけます (ここではいくつかのアルゴリズムの議論が必要になる場合があります)。
3. size(X) から 0 まで繰り返します。各繰り返しで、文字列が YYZ'Z' になるように両端から X を削除し、文字列を中央で分割して YZ == Y'Z' であることを確認し、確認された場合は True を返します。 .
4. 反復後、false を返します。