コードセグメント内のパターンの検出

Question

2つ以上のテキストのサンプル、具体的にはコードのセグメントを指定すると、サンプルが異なる場所を検出し、各サンプルに一致するパターンを形成する最も効率的な方法は何ですか？例えば

、次のコードサンプルを与えられた：

cd ~/workspaces/project/tmp1/bin 
rsync --recursive --progress /data/local/documents* data 

cd ~/workspaces/project/we32usZ/bin 
rsync --recursive --progress /data/local/lib* data 

cd ~/workspaces/project/oiususs/bin 
rsync --recursive --progress /data/local/usr* data 

どのように私は（$ VARNは、ワイルドカード変数を示します）、このパターンを推測でしょうか？

cd ~/workspaces/project/$var1/bin 
rsync --recursive --progress /data/local/$var2* data 

私の最初のアプローチは、差はその後、テキストの「変数」の部分が終わるところを探し、発見されるまで、各i番目の文字を比較し、二つのサンプルを比較して、他のサンプルのためにこれを繰り返すことです。しかし、これは非常に非効率的であるように思われ、明らかにテキストが最初から非常に似ていると仮定します。より良い方法がありますか？

Answer 1

上記の例のように、multiple sequence alignmentのバリエーションが役立ちます。基本的には、動的プログラミングを使用して、コードのすべてのセグメントで保存された部分文字列を探しています。