サーチ…
最短共通共通計画問題基本情報
最短共通スーパーシーケンスは、このタスクの外部関数として使用できる最も長い共通サブシーケンスに密接に関連する問題です。最短共通スーパーシーケンス問題は、最も長い共通サブシーケンス問題に密接に関連する問題である。
最短の共通スーパーシーケンス(scs)は最小の長さの共通のスーパーシーケンスです。最短の共通スーパーシーケンス問題では、2つのシーケンスX
とY
が与えられ、タスクはこれらのシーケンスの可能な最短の共通スーパーシーケンスを見つけることである。一般的に、scは一意ではありません。
与えられた二つの配列X = <x1,...,xm>
およびY = <y1,...,yn>
シーケンスU = <u1,...,uk>
の一般的なスーパーシーケンスであるX
とY
の場合は、 U
はX
とY
スーパーシーケンスです。換言すれば、文字列の最短の共通スーパー配列x
及びy
最短の文字列であり、 z
の両方ように、 x
及びy
のサブシーケンスであるz
。
2つの入力シーケンスに対して、最も長い共通部分シーケンス(lcs)から容易にscsを形成することができる。例えば、 X[1..m]=abcbdab
かつY[1..n]=bdcaba
場合、lcsはZ[1..r]=bcba
。記号の順番を保ったまま非lcsシンボルを挿入すると、sc U[1..t]=abdcabdab
。
2つの入力シーケンスに対して、 r+t=m+n
であることは明らかである。しかし、3つ以上の入力シーケンスの場合、これは成立しません。 lcsとscsの問題は二重の問題ではないことにも注意してください。
ストリングS1,S2,...,Sl
セットのスーパーストリングであるストリングS
を見つけるより一般的な問題については、問題はNP完全です。また、平均的な場合には良好な近似が見出されるが、最悪の場合には見出されない。
最短共通共起問題の例:
時間複雑度: O(max(m,n))
C#における最短共通共起問題の実装
public class ShortestCommonSupersequence
{
private static int Max(int a, int b)
{
return a > b ? a : b;
}
private static int Lcs(string x, string y, int m, int n)
{
var l = new int[m + 1, n + 1];
for (var i = 0; i <= m; i++)
{
for (var j = 0; j <= n; j++)
{
if (i == 0 || j == 0) l[i, j] = 0;
else if (x[i - 1] == y[j - 1]) l[i, j] = l[i - 1, j - 1] + 1;
else l[i, j] = Max(l[i - 1, j], l[i, j - 1]);
}
}
return l[m, n];
}
private static int Scs(string x, string y)
{
int m = x.Length, n = y.Length;
int l = Lcs(x, y, m, n);
return m + n - l;
}
public static int Main(string x, string y)
{
return Scs(x, y);
}
}