LCS(Longest Common Subsequence)文字列最長共通サブストリングアルゴリズム

LCS(Longest Common Subsequence)アルゴリズムは、2つの文字列の最も長い共通サブ列を見つけるために使用される.アルゴリズムの原理:(1)2つの文字列をそれぞれ行と列でマトリクスに構成します.(2)各ノードの行列文字が同じかどうかを計算し,同じ場合は1とする.(3)値が1の最長対角線を見つけ出すことで最長共通サブストリングを得る.人民共和時代には0,0,0,0,0,0華0,0,0,0,0,0,0人1,0,0,0民0,1,0,0,0,0共0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0をさらに高めるアルゴリズムとして、文字の同じノード(1)の値に左上隅(d[i-1,j-1])の値を加えることで、最大共通サブストリングの長さを得ることができます.これにより、行番号と最大値を条件に最大サブ列を切り取ることができます.人民共和時代中0,0,0,0,0,0華0,0,0,0,0,0人1,0,0,0,0,0民0,2,0,0,0,0,0,0,0共0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0アルゴリズム実現:

public static string LCS(string s1, string s2)
{
    if (s1 == s2)
        return s1;
    else if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
        return null;

    var d = new int[s1.Length, s2.Length];

    var index = 0;
    var length = 0;

    for (int i = 0; i < s1.Length; i++)
    {
        for (int j = 0; j < s2.Length; j++)
        {
            //     
            var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;

            //       = "1 +     " : "0"
            d[i, j] = s1[i] == s2[j] ? 1 + n : 0;

            //       ，        
            if (d[i, j] > length)
            {
                length = d[i, j];
                index = i;
            }
        }
    }

    return s1.Substring(index - length + 1, length);
}

変換元:http://www.rainsts.net/article.asp?id=767