Блог

Определите степень строки M как количество раз, когда она появляется в другой строке S. Например, M = «aba» и S = «abeba», степень M равна 2. Учитывая набор строк и целое число N, найдите строку минимальной длины, чтобы сумма степеней всех строк в наборе была не менее N.

Например, набор {«ab», «bd», «abd», «babd», «abc»}, N = 4, ответом будет «babd». Она содержит «ab», «abd», «babd» и «bd» один раз.

N <= 100, M <= 100, длина каждой строки в наборе <= 100. Строки в наборе состоят только из прописных и строчных букв.

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

У меня есть алгоритм полиномиального времени, который я слишком ленив, чтобы кодировать. Но я опишу это для вас.

Сначала сделайте каждую строку в наборе плюс пустую строку узлами графика. Пустые строки соединяются друг с другом строками, и наоборот. Если конец одной строки перекрывается с началом другой, они также соединяются. Если две строки могут перекрываться на разную величину, они получают несколько ребер. (Так что это не совсем график …)

Каждое ребро получает стоимость и значение. Стоимость — это то, на сколько символов вам нужно расширить строку, на которую вы строите, чтобы перейти от старого конца к новому концу. (Другими словами, длина второй строки минус длина перекрытия.) к наличию этой. Значение — это количество новых строк, которые вы завершили, которые пересекают барьер между первой и последней строками.

Ваш пример был {«ab», «bd», «abd», «babd», «abc»}. Вот (cost, value) пары для каждого перехода.

  from  ->   to  : (value, cost)
 ""    ->   "ab": (    1,    2)
 ""    ->   "bd": (    1,    2)
 ""    ->  "abd": (    3,    3) # we added "ab", "bd" and "abd"
 ""    -> "babd": (    4,    4) # we get "ab", "bd", "abd" and "babd"
 ""    ->  "abc": (    2,    3) # we get "ab" and "abc"
 "ab"  ->     "": (    0,    0)
 "ab"  ->   "bd": (    2,    1) # we added "abd" and "bd" for 1 character
 "ab"  ->  "abd": (    2,    1) # ditto
 "ab"  ->  "abc": (    1,    1) # we only added "abc"
 "bd"  ->     "": (    0,    0) # only empty, nothing else starts "bd"
"abd"  ->     "": (    0,    0) 
  

«babd» -> «»: ( 0, 0)
«babd» -> «abd»: (0, 0) # перекрывается, но ничего не добавлено.
«abc» -> «»: ( 0, 0)

Хорошо, все это настройка. Зачем нам нужен этот график?

Хорошо, обратите внимание, что если мы начнем с «» со стоимостью 0 и значением 0, затем пройдем путь через график, который создает строку. В нем правильно указана стоимость и указана нижняя граница значения. Значение может быть выше. Например, если бы ваш набор был {«ab», «bc», «cd», «abcd»}, то путь «» -> «ab» -> «bc» -> «cd» привел бы к строке «abcd» со стоимостью 4 и прогнозируемым значением 3. Но в этой оценке значения не учитывался тот факт, что мы соответствовали «abcd».

Однако для любой заданной строки, состоящей только из подстрок из набора, существует путь через график, который имеет правильную стоимость и правильное значение. (При каждом выборе вы хотите выбрать самую раннюю начальную строку соответствия, которую вы еще не подсчитали, и из них выбрать самую длинную из них. Тогда вы никогда не пропустите ни одного совпадения.)

Итак, мы перевели нашу задачу с построения строк на построение путей через граф. Что мы хотим сделать, так это создать следующую структуру данных:

 for each (value, node) combination:
    (best cost, previous node, previous value)
  

Заполнение этой структуры данных является проблемой динамического программирования. После заполнения мы можем просто проследить по нему, чтобы найти, какой путь на графике привел нас к этому значению с такой стоимостью. Учитывая этот путь, мы можем вычислить строку, которая это сделала.

Насколько это быстро? Если в нашем наборе есть K строки, то нам нужно только заполнить K * N значения, каждому из которых мы можем предоставить максимум K кандидатов на новые значения. Что делает поиск пути O(K^2 * N) проблемой.

Итак, вот мой подход. На первой итерации мы создаем пул из начальных строк. После этого:

1. Мы выбираем из пула строку, имеющую минимальную длину и сумму степеней=N. Если мы нашли такую строку, мы просто возвращаем ее.
2. Мы отфильтровываем из пула все строки со степенью меньше максимальной. Мы работаем только с наилучшими возможными комбинациями строк.
3. Мы создаем все варианты из текущего пула и начальных строк. Здесь нам нужно принять во внимание, что строки могут перекрываться. Допустим, строка «aba» и «ab» (из начальных строк) может выдавать: ababa, abab, abaab (мы не включаем «aba», потому что она уже была у нас в пуле, и нам нужно двигаться дальше).
4. Мы отфильтровываем дубликаты, и это наш следующий пул.
5. Повторите все с точки 1.

Метод FindTarget() принимает целевую сумму в качестве параметра. FindTarget(4) решит примерную задачу.

 public class Solution
{
    /// <summary>
    /// The initial strings.
    /// </summary>
    string[] stringsSet;
    Tuple<string, string>[][] splits;
    public Solution(string[] strings)
    {
        stringsSet = strings;
        splits = stringsSet.Select(s => ProduceItemSplits(s)).ToArray();
    }

    /// <summary>
    /// Find the optimal string.
    /// </summary>
    /// <param name="N">Target degree.</param>
    /// <returns></returns>
    public string FindTarget(int N)
    {
        var pool = stringsSet;
        while (true)
        {
            var poolWithDegree = pool.Select(s => new { str = s, degree = GetN(s) })
                .ToArray();
            var maxDegree = poolWithDegree.Max(m => m.degree);
            var optimalString = poolWithDegree
                .Where(w => w.degree >= N)
                .OrderBy(od => od.str.Length)
                .FirstOrDefault();
            if (optimalString != null) return optimalString.str; // We found it
            var nextPool = poolWithDegree.Where(w => w.degree == maxDegree)
                .SelectMany(sm => ExpandString(sm.str))
                .Distinct()
                .ToArray();
            pool = nextPool;
        }
    }
    /// <summary>
    /// Get degree.
    /// </summary>
    /// <param name="candidate"></param>
    /// <returns></returns>
    public int GetN(string candidate)
    {

        var N = stringsSet.Select(s =>
        {
            var c = Regex.Matches(candidate, s).Count();
            return c;
        }).Sum();
        return N;
    }

    public Tuple<string, string>[] ProduceItemSplits(string item)
    {
        var substings = Enumerable.Range(0, item.Length   1)
            .Select((i) => new Tuple<string, string>(item.Substring(0, i), item.Substring(i, item.Length - i))).ToArray();
        return substings;
    }

    private IEnumerable<string> ExpandStringWithOneItem(string str, int index)
    {
        var item = stringsSet[index];
        var itemSplits = splits[index];
        var startAttachments = itemSplits.Where(w => str.StartsWith(w.Item2) amp;amp; w.Item1.Length > 0)
            .Select(s => s.Item1   str);
        var endAttachments = itemSplits.Where(w => str.EndsWith(w.Item1) amp;amp; w.Item2.Length > 0)
            .Select(s => str   s.Item2);
        return startAttachments.Union(endAttachments);
    }

    public IEnumerable<string> ExpandString(string str)
    {
        var r = Enumerable.Range(0, splits.Length - 1)
                .Select(s => ExpandStringWithOneItem(str, s))
                .SelectMany(s => s);
        return r;
    }
}

static void Main(string[] args)
{
    var solution = new Solution(new string[] { "ab", "bd", "abd", "babd", "abc" });
    var s = solution.FindTarget(150);
    Console.WriteLine(s);
}