解を式で表してそれを簡単にする (右端)-(左端) の長さの重複を認めた集合をW, (上端)-(下端) の長さの重複を認めた集合をH, とすると解は Σw*h (w∈W, h∈H) で表せる。 これにはよくある式変形により Σw*h (w∈W, h∈W) =Σw(w∈W) * Σh(h∈H) たとえば w0*h0+w0*…

部分文字列の文字の順序は関係ない つまり、部分文字列は任意の順序に並び替えることができる。 隣接する異なる2文字を入れ替えられることを示す。 AB →BBB →BBAA →BBBBA →BA したがって、任意の隣接する2文字は入れ替えられる。なのでバブルソートの要領で…