最長共通部分列問題

longest-common-substring.png

概要

  • 部分文字列….文字列のいくつかの要素を取り除いて出来た文字列のこと[1]
  • 最長共通部分文字列…..与えられた2つの文字列から取り出した部分文字列のうち、同一かつ最長のもの

やり方

考慮する文字列の長さをだんだん長くしながら最長共通部分列を更新する。

たとえば、
p=abcbdab
q=bdcaba
の2つの最長共通部分列は
bcaba
である。
たとえば

こんなの何に使うかって?

何に役に立つの?

  • gitを使ってるとわかりますが、ソースコードを比較して差分を取る操作(コード1行を最長共通部分文字列問題の1文字としてみる)
  • 音声認識において入力データとパターンを比較したりする場合

たとえば、

  • ソースコードを比較して差分をとる操作(コード1行を最長共通部分列問題の1文字としてみる)無料ソフトのWinMeargeがやってること?
  • 音声認識において入力データとパターンを比較する

など、ひろーく使われてそうだね。

p=abcbdab
q=bdcaba

この問題を解くには、考慮する列の長さをだんだんと長くしながら、最長共通部分列を更新していけばいい。

#include <string>
#include <algorithm>
using namespace std;
LongestCommonSubstring(string p,string q){
int *lcs=new int[p.size()*q.size()];//これがメモ用の表
for(int y=0;y<p.size();y++){
    for(int x=0;x<q.size();x++){
        int d=p[y]==q[x] ?1:0;
        lcs[y*q.size()+x]=max(lcs[(y-1)*q.size()+(x-1)]+d,
                                       lcs[(y-1)*q.size()+x],
                                       lcs[(y)*q.size()+(x-1)]);
    }
}
}

algorithmのmax関数は3つの値を引数にとったりしたっけ??まぁ、とにかく、意味的にはこんなかんじ。
このメモ用の表lcs[]を図示してみるとこんなかんじ
q
- b d c a b a
- 0 0 0 0 0 0 0
a 0 0 0 0 1 1 1
b 0 1 1 1 1 1 1
c 0 1 1 2 2 2 2
b 0 1 1 2 2 3 3
d 0 1 1 2 2 3 3
a 0 1 1 2 2 3 4
b 0 1 1 2 2 3 4
書けなかったけど、縦がpね。
表の1番右下に入る数字が最長共通部分列の長さになる。
そこへ至る左上から右下へのパスをたどると最長共通部分列が得られる。
q
- b d c a b a
- 0 0 0 0 0 0 0
a 0 0 0 0 1 1 1
b 0 1 1 1 1 1 1
c 0 1 1 2 2 2 2
b 0 1 1 2 2 3 3
d 0 1 1 2 2 3 3
a 0 1 1 2 2 3 4
b 0 1 1 2 2 3 4
Bibliography
1. データ構造とアルゴリズム (新・情報 通信システム工学….大学の教科書としても使われている。難しかった。結構図があっていい。

dynamic-programming

サポートサイト Wikidot.com dynamic-programming