Блог

Допустим, у нас есть список объектов узла со свойством Value . Существует ли эффективный по времени алгоритм для связывания пар узлов с одинаковым значением только в пределах самого длинного повторяющегося диапазона (диапазонов) узлов?

Перекрытие разрешено, поэтому допускается несколько самых длинных промежутков пары узлов, если они имеют одинаковую длину.

Свойство Value неприводимо к символу, и поэтому алгоритм «самой длинной повторяющейся подстроки» не является ответом.

Пример:

 INPUT:
Node Values =
{ AA, BB, CC, DD, AA, BB, CC, AA, BB, CC, DD, EE, BB, CC, DD, EE, FF, EE, FF } // Values
  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16  17  18   // indices

OUTPUT:
Edges (from_node_index, to_node_index) =
{
  (00-07, 01-08, 02-09, 03-10),
  (08-12, 09-13, 10-14, 11-15),
  (15-17, 16-18)
}
  

Вот моя наивная попытка с использованием C #, которая, я думаю, выполняется с O (n ^ 2 log n) временной сложностью.

 for (int i = 0; i < m_nodes.Count - 1; i  )
{
    int first_j = -1;
    int range = 0;  // maximum number of repeated nodes in node range
    int k = 0;      // current number of repeated nodes in node range

    for (int j = i   1; j < m_nodes.Count; j  )
    {
        if (m_nodes[i].Value == m_nodes[j].Value)
        {
            k = 0;
            do
            {
                k  ;
                if ((j   k) == m_nodes.Count) break;
            } while (m_nodes[i   k].Value == m_nodes[j   k].Value);

            if (k > range)
            {
                range = k;

                first_j = j;
                j  = range; // skip repeating nodes
            }
        }
    }

    if (range > 0)
    {
        if (first_j > i)
        {
            for (int x = 0; x < range; x  )
            {
                if (first_j >= 0)
                {
                    Edge edge = new Edge();
                    if (edge != null)
                    {
                        edge.Id =   count;
                        edge.Source = m_nodes[i   x];
                        edge.Target = m_nodes[first_j   x];
                        edge.Label = m_nodes[first_j   x].Text   " = "   m_nodes[first_j   x].Value.ToString();
                        edge.Range = range;
                        edge.NumberInRange = x   1;
                        m_edges.Add(edge);
                    }
                }
            }
        }
    }
}
  

Я чувствую, что динамическое программирование может быть ответом, но я с этим не знаком.

Вот полный исходный код: https://yadi.sk/d/aDdN9slB0H7BQA

Заранее благодарю.