Как создать кратчайшую строку из строк?

Эта задача относится к сложным как в реализации так и в скорости задачам. Она может быть решена с помощью модернизированного алгоритма Ахо-Корасик http://e-maxx.ru/algo/aho_corasick . Конкретные детали реализации там же в предпоследнем абзаце (Нахождение кратчайшей строки, содержащей вхождения одновременно всех образцов) .

Важно! сложность будет порядка 2^n где n - количество строк.

Может искать эту задачу по запросу shortest common superstring она NP-полная.

Возможна упрощённая постановка задачи.

Если у нас есть 2 строки, то вариантов их склеивания четыре:
1. В исходном порядке.
2. В обратном порядке.
3. Первая строка внутри второй.
4. Вторая строка внутри первой.

Рассмотрим сочетания из n строк по r строк (которых Сnr).
Будем называть их сочетаниями ранга r.
Оптимум для каждого такого сочетания достигается при одной из r! внутренних перестановок. Упрощение постановки - в предположении, что каждый новый вариант оптимальной перестановки ранга r+1 можно получить, склеивая одну из оптимальных перестановок ранга r с недостающей строкой.

Оптимизация вычислений - в том, что используется массив сочетаний вместо массива размещений (которых в r! раз больше), а для каждой новой перестановки ранга (r+1) проверяется всего r вариантов склеивания вместо (r+1)!.
В то же время, это "жадный" вариант без перебора. Поэтому строка результата может оказаться длинее оптимальной.

В упрощённой постановке каждое сочетание можно описать уникальным числовым ключом-маской, битовое представление которого содержит единицы в позициях, соответствующих используемым строкам. Ключи предыдущего ранга получаются путём инверсии одной из единиц, а ключи следующего ранга - путём инверсии одного из нулей.

Каждому такому ключу соответствует битовая строка результата, которая допускает сжатие каждых 8 битовых символов в один упакованный байтовый. Решение задачи получается путём обхода всех сочетаний с повышением их ранга.

Для случая n строк всего получается 2n вариантов сочетаний всех рангов, и это следует из формулы бинома Ньютона для (1+1)n. Так, для случая n = 30 требуется перебрать
230 = 1073741824 сочетаний, а максимальная размерность массива сочетаний достигается при r=15 и равна С3015=155117520.

Инициализация проводится для ранга r=2 среди уникальных строк (не входящих в другие строки) путём попарного склеивания. Далее в цикле по r массив сочетаний ранга r трансформируется в массив сочетаний ранга r+1. В конце цикла остаётся массив из одного элемента с ключом из единиц и результирующей строкой.

Отличие предлагаемого решения от алгоритма Ахо-Корасик - в том, что перебираются не битовые строки (если при построении бора нет символов, увеличивающих количество поглощаемых образцов, вводится промежуточная вершина), а сочетания исходных образцов. В то же время обход графа в ширину по сложности равнозначен перебору сочетаний. Таким образом, реальная сложность алгоритма Ахо - Корасик при плохом склеивании строк может оказаться равной 2mn, и вопрос о сравнении скорости алгоритмов остаётся актуальным.

Программа на языке PHP:

set_time_limit(300);
function bits($num, $n){
    return substr(sprintf("%032b", $num), -$n, $n);
}
function print_array($text, $arr){
    print($text."[");
    foreach($arr as $key => $item){
        printf("%d => \"%s\", " , $key, (string)$item);
    }
    print "]";  
}
function glue($s1, $s2){
    global $count_glue;
    $count_glue++;
    $len1 = strlen($s1);
    $len2 = strlen($s2);
    if($s1 == $s2){
        $res = $s1;     // строки равны
    }elseif(($len1 < $len2) && (strpos($s2, $s1) !== false)){
        $res = $s2;     // первая строка есть подстрока второй
    }elseif(($len1 > $len2) && (strpos($s1, $s2) !== false)){
        $res = $s1;     // вторая строка есть подстрока первой
    }else{              // ищем наибольшие общие фраагменты с краёв
        $lmin = min($len1,$len2);
        $len12 = 0;
        $len21 = 0;
        for($l = 1; $l<$lmin; $l++){
            if(substr($s1, -$l, $l) == substr($s2,0, $l))   $len12 = $l;    
            if(substr($s1, 0, $l) == substr($s2,-$l, $l))   $len21 = $l;    
        }
        if($len12 > $len21){
            $res = $s1.substr($s2, $len12, $len2-$len12);
        }else{
            $res = $s2.substr($s1, $len21, $len1-$len21);
        }           
    }
    //print("&quot;$s1&quot; + &quot;$s2&quot; = &quot;$res&quot;&emsp;");
    return $res;    
}
function chars_bits_arrays(){
    global $chars2bits, $bits2chars;
    for($b = 0; $b < 256; $b++){
        $chars = chr($b);
        $bits = sprintf("%08b", $b);
        $bits2chars[$bits] = $chars;
        $chars2bits[$b] = $bits;
    }
}
function pack_bits($bits){
    global $bits2chars;
    $len_bits = strlen($bits);
    $cnt_chars = ceil($len_bits/8);
    $bits8 = str_pad($bits, 8*$cnt_chars, "0");
    $chars = chr($len_bits);
    for($c = 0; $c < $cnt_chars; $c++){
        $chars .= $bits2chars[substr($bits8, 8*$c, 8)]; 
    }
    return $chars;
};
function unpack_bits($chars){
    global $chars2bits;
    $end_chars = strlen($chars)-1;
    $len_bits = ord($chars[0]);
    $bits = "";
    for($c = 1; $c < $end_chars; $c++){
        $bits .= $chars2bits[ord($chars[$c])];
    }
    $last_char = $chars2bits[ord($chars[$end_chars])];
    $bits .= substr($last_char, 0, $len_bits - 8*($end_chars-1));
    return $bits;
}
function print_packed($text, $str_packed, $n=31){
    print($text."[");
    foreach($str_packed as $key => $item){
        printf("&quot;$key&quot; => &quot;%s&quot;, " , unpack_bits($item));
    }
    print "]";  
}
function unique_strings(&$strings){
    $cnt = count($strings);
    $delete = [];
    for($k1 = 0;  $k1 < $cnt; $k1++){
        $s1 = $strings[$k1];
        $len1 = strlen($s1);
        for($k2 = 0; $k2 < $k1; $k2++){
            $s2 = $strings[$k2];
            $len2 = strlen($s2);
            if($s1 == $s2){
                $delete[] = $k1;
            }elseif(empty($s1) || (($len1 < $len2) && (strpos($s2, $s1) !== false))){
                    $delete[] = $k1;        // первая строка есть подстрока второй
            }elseif(empty($s2) || (($len2 < $len1) && (strpos($s1, $s2) !== false))){
                    $delete[] = $k2;        // вторая строка есть подстрока первой
            }
        }
    }
    foreach($delete as $key){
        unset($strings[$key]);
    }
    $strings = array_slice($strings, 0);
}
function rank2($strings){
    $cnt = count($strings);
    $result = [];
    for($k1 = 0;  $k1 < $cnt; $k1++){
        $s1 = $strings[$k1];
        for($k2 = 0; $k2 < $k1; $k2++){
            $s2 = $strings[$k2];
            $g = glue($s1, $strings[$k2]);
            $key = (1 << $k1) | (1 << $k2);
            $result[$key] = pack_bits($g);
        }
    }
    return $result;
}
function inc_rank(&$supers, &$strings, &$r){
    $n = count($strings);
    $result = [];
    foreach($supers as $key => $packed){
        $super = unpack_bits($packed);
        $len_super = strlen($super);
        //print "<br>$key=>&quot;$super&quot;: ";
        for($k = 0; $k < $n; $k++){
            $bit = 1 << $k;
            if (($key & $bit) == 0){
                $key1 = $key | $bit;
                $s = $strings[$k];
                $len_s = strlen($s);
                if($super == $s){
                    $result[$key1] = $packed;
                }else{
                    //print "&emsp;$key1 =>";                           
                    $g = glue($super, $strings[$k]);
                    if(!array_key_exists($key1, $result)){
                        $result[$key1] = pack_bits($g);
                    //  print "-новое!";
                    } elseif(strlen($g) < ord($result[$key1][0])){
                        $result[$key1] = pack_bits($g);
                    //  print "-лучше!";
                    } 
                }
            }
        }
    }
    return($result);
}
function the_best_combi($strings){
    global $count_glue;
    $start_timer = microtime(true);
    $count_glue = 0;
    print_array("<br><br>***** Склеивание массива строк: *****<br>strings = ", $strings);
    unique_strings($strings);
    print_array("<br><br>Уникальные строки:<br>unique_strings = ", $strings);
    //print "<br><br>";
    $cnt_strings = count($strings);
    $supers = rank2($strings);
    //print_packed("<br><br>*** Сочетания ранга 2: ***<br> ", $supers, $cnt_strings);
    for($r=3; $r <= $cnt_strings; $r++){
        //print "<br>";
        $result = inc_rank($supers, $strings, $r);
        if($result === false){
            break;
        } 
        $supers = $result;
        //print_packed("<br><br>*** Сочетания ранга $r: ***<br>", $supers, $cnt_strings);
    }
    if($result === false){
        $new = [];
        foreach($strings as $str){
            $new[] = $str;
        }
        $strings = $new;
        $supers = the_best_combi($strings);
    }
    $time = microtime(true) - $start_timer;
    print "<br>Время, секунд: $time";
    print "<br>Склеено пар строк: $count_glue";
    print_packed("<br>Результат:&emsp;", $supers, $cnt_strings);
}
$chars2bits = [];
$bits2chars = [];
chars_bits_arrays();
$count_glue = 0;
$strings = ["000", "001", "100", "011"];
the_best_combi($strings);
$strings = ["000", "001", "010", "011", "100", "101", "110", "111", 
            "000", "001", "010", "011", "100", "101", "110", "111"];
the_best_combi($strings);
$strings = ["0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
            "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"];
the_best_combi($strings);
$strings = ["010101100", "100010001", "1100010001000", "1000010101100", 
            "01000001010", "1000100101", "0100001100110", "00110111",
            "1010101000", "0100011001", "001000111010", "1000111011", 
            "00110011100", "11000110001", "10001110111", "1000111001111"];
the_best_combi($strings);

Результаты:

***** Склеивание массива строк: *****
strings = [0 => "000", 1 => "001", 2 => "100", 3 => "011", ]
Уникальные строки:
unique_strings = [0 => "000", 1 => "001", 2 => "100", 3 => "011", ]
Время, секунд: 0.00200009346008
Склеено пар строк: 22
Результат: ["15" => "100011", ]
***** Склеивание массива строк: *****
strings = [0 => "000", 1 => "001", 2 => "010", 3 => "011", 4 => "100", 5 => "101", 6 => "110", 7 => "111", 8 => "000", 9 => "001", 10 => "010", 11 => "011", 12 => "100", 13 => "101", 14 => "110", 15 => "111", ]
Уникальные строки:
unique_strings = [0 => "000", 1 => "001", 2 => "010", 3 => "011", 4 => "100", 5 => "101", 6 => "110", 7 => "111", ]
Время, секунд: 0.117007017136
Склеено пар строк: 988
Результат: ["255" => "1110100011", ]
***** Склеивание массива строк: *****
strings = [0 => "0000", 1 => "0001", 2 => "0010", 3 => "0011", 4 => "0100", 5 => "0101", 6 => "0110", 7 => "0111", 8 => "1000", 9 => "1001", 10 => "1010", 11 => "1011", 12 => "1100", 13 => "1101", 14 => "1110", 15 => "1111", ]
Уникальные строки:
unique_strings = [0 => "0000", 1 => "0001", 2 => "0010", 3 => "0011", 4 => "0100", 5 => "0101", 6 => "0110", 7 => "0111", 8 => "1000", 9 => "1001", 10 => "1010", 11 => "1011", 12 => "1100", 13 => "1101", 14 => "1110", 15 => "1111", ]
Время, секунд: 66.4247989655
Склеено пар строк: 524152
Результат: ["65535" => "1111011001010000111", ]
***** Склеивание массива строк: *****
strings = [0 => "010101100", 1 => "100010001", 2 => "1100010001000", 3 => "1000010101100", 4 => "01000001010", 5 => "1000100101", 6 => "0100001100110", 7 => "00110111", 8 => "1010101000", 9 => "0100011001", 10 => "001000111010", 11 => "1000111011", 12 => "00110011100", 13 => "11000110001", 14 => "10001110111", 15 => "1000111001111", ]
Уникальные строки:
unique_strings = [0 => "1100010001000", 1 => "1000010101100", 2 => "01000001010", 3 => "1000100101", 4 => "0100001100110", 5 => "00110111", 6 => "1010101000", 7 => "0100011001", 8 => "001000111010", 9 => "00110011100", 10 => "11000110001", 11 => "10001110111", 12 => "1000111001111", ]
Время, секунд: 15.895909071
Склеено пар строк: 53157
Результат: ["8191" => "100011100111100011101110001001010001100111000010101100011000100010001110101010000010100001100110111", ]