2014-08-03

二つの文字列の融合

融合っていうのは、「あいうえお」と「うえおかき」を混ぜて足して「あいうえおかき」にするケースのこと。後者の先頭の「うえお」を前者へ融かし合わせるので融合と言ったけど、それで良いのかよくわからない。ちゃんとしたアルゴリズムありそうだけど、見つけることができなかったので、後方から検索していくみたいな感じで書いた。

function fuse(a, b) {
  var i = 0;
  var s = '';
  var j = 0;

  for (i = b.length; i > 0; i--) {
    s = b.substring(0, i);
    j = a.lastIndexOf(s);

    if (j >= 0 && j + s.length === a.length) {
      break;
    }
  }

  return a + b.substring(i);
}

console.log('abcde + efg   =', fuse('abcde', 'efg'));
console.log('abcde + cdefg =', fuse('abcde', 'cdefg'));
console.log('abcde + fg    =', fuse('abcde', 'fg'));
console.log('abcde + abcde =', fuse('abcde', 'abcde'));
console.log('abcde + bcd   =', fuse('abcde', 'bcd'));

文字列bを一文字ずつ減らしながら文字列aの後ろから検索していく。正規表現だとコストが高そうだったのでlastIndexOf()でやってる。このままだと途中に出てきてもOKになってしまうので、インデックスに検索した文字列の長さを足して文字列aの長さになるかどうかをチェックすることで、文字列aの最後に出てきているかどうかもちゃんと確認する。減らしながら探しているので、見つかったらそこで終了すれば良い。最後のインデックスを使って文字列bを切り詰め連結すれば融合した文字列が作り出せる。

$ node fuse.js
abcde + efg   = abcdefg
abcde + cdefg = abcdefg
abcde + fg    = abcdefg
abcde + abcde = abcde
abcde + bcd   = abcdebcd

大丈夫そう。