Самый длинный общий префикс для n строки

Question

Указанная n строка максимальной длины m. Как мы можем найти самый длинный общий префикс, совместно используемый, по крайней мере, двумя строками среди них?

Пример: [ «цветок», «поток», «привет», «флот»]

Ответ: фло

Я думал о строительстве TRIE для всей строки, а затем проверить глубочайший узел (наиболее длинный), который разветвляется на две и более подстрок (удовлетворяет общности). Это берет O (n * m) время и пространство. Есть ли лучший способ сделать это?

Answer 1

Я бы выбрал их, что вы можете сделать в n lg n раз. Тогда любые строки с общими префиксами будут расположены рядом друг с другом. Фактически, вы должны иметь возможность указывать указатель того индекса, который вы сейчас просматриваете, и работать с ним довольно быстро.

Answer 2

Решение этой проблемы trie. [n это число строк, S это самая длинная строка]

(1) put all strings in a trie 
(2) do a DFS in the trie, until you find the first vertex with more then 1 "edge". 
(3) the path from the root to the node you found at (2) is the longest commin prefix. 

Там нет никакой возможности быстрее решения то [с точки зрения большой нотации O], в худшем случае, все ваши строки идентичны - и вам нужно прочитать их все, чтобы это узнать.

Answer 3

Как совершенно другой ответ от моего другого ответа ...

Вы можете, с одним проходом, ковш каждой строки на основе первой букве.

С помощью другого прохода вы можете отсортировать каждое ведро на основании его второго позже. (Это известно как поразрядная сортировка, который O(n*m) и O(n) с каждым проходом.) Это дает базовый префикс 2.

Вы можете безопасно удалить из набора данных каких-либо элементы, которые не имеют префикса 2.

Вы можете продолжить сортировку радикса, удалив элементы без общего префикса p, так как p подходит к m.

Это даст вам то же самое время, что и при использовании trie, но всегда будет быстрее, чем trie, поскольку trie должен смотреть на каждый символ в каждой строке (поскольку он входит в структуру), в то время как этот подход гарантированно смотреть на 2 символа на строку, и в этот момент она отбирает большую часть набора данных.

Худший случай - все равно, что каждая строка идентична, поэтому она имеет одинаковую большую нотацию O, но будет быстрее во всех случаях, так как гарантировано использовать меньшее количество сравнений, поскольку в любом «не худшем случае», есть персонажи, которые никогда не нужно посещать.

Answer 4

Зачем использовать trie (который принимает время O (mn) и пространство O (mn), просто используйте базовый метод грубой силы. Первый цикл, найдите кратчайшую строку как minStr, которая принимает o (n) время, второе цикл, сравните один за другим с этим minStr и сохраните переменную, которая указывает самый правый индекс minStr, этот цикл принимает O (mn), где m - кратчайшая длина всех строк.Код, как показано ниже,

public String longestCommonPrefix(String[] strs) { 
    if(strs.length==0) return ""; 
    String minStr=strs[0]; 

    for(int i=1;i<strs.length;i++){ 
     if(strs[i].length()<minStr.length()) 
      minStr=strs[i]; 
    } 
    int end=minStr.length(); 
    for(int i=0;i<strs.length;i++){ 
     int j; 
     for(j=0;j<end;j++){ 
      if(minStr.charAt(j)!=strs[i].charAt(j)) 
       break; 
     } 
     if(j<end) 
      end=j; 
    } 
    return minStr.substring(0,end); 
} 

Answer 5

public String longestCommonPrefix(String[] strs) { 

    if (strs == null || strs.length == 0) 
     return ""; 

    char[] c_list = strs[0].toCharArray(); 
    int len = c_list.length; 
    int j = 0; 
    for (int i = 1; i < strs.length; i++) { 
     for (j = 0; j < len && j < strs[i].length(); j++) 
      if (c_list[j] != strs[i].charAt(j)) 
      break; 
     len = j; 
    } 

    return new String(c_list).substring(0, len); 

} 

Answer 6

Бывает, что блочная сортировка (Radix сортировка) описывается corsiKa может быть расширена таким образом, что все строки в конце концов, помещает один в ведре, и в тот момент, Известна LCP для такой одинокой строки. Кроме того, известно также разрушение каждой строки; он длиннее, чем LCP. Сортировка ковша деформирует конструкцию массива суффиксов, но только частично. Те сравнения, которые не выполняются (как описано corsiKa), действительно представляют те части суффиксных строк, которые не добавлены в массив суффикса. Наконец, этот метод позволяет определять не только LCP и shustrings, но также легко найти те подпоследовательности, которые отсутствуют в строке.

Answer 7

Поскольку мир явно выпрашивая ответ на Swift, вот мое;)

func longestCommonPrefix(strings:[String]) -> String { 

    var commonPrefix = "" 
    var indices = strings.map { $0.startIndex} 

outerLoop: 

    while true { 
     var toMatch: Character = "_" 

     for (whichString, f) in strings.enumerate() { 

      let cursor = indices[whichString] 

      if cursor == f.endIndex { break outerLoop  } 

      indices[whichString] = cursor.successor() 

      if whichString == 0  { toMatch = f[cursor] } 
      if toMatch != f[cursor] { break outerLoop  } 
     } 

     commonPrefix.append(toMatch) 
    } 

    return commonPrefix 
} 

Swift 3 Update:

func longestCommonPrefix(strings:[String]) -> String { 

    var commonPrefix = "" 
    var indices = strings.map { $0.startIndex} 

    outerLoop: 

     while true { 
      var toMatch: Character = "_" 

      for (whichString, f) in strings.enumerated() { 

       let cursor = indices[whichString] 

       if cursor == f.endIndex { break outerLoop  } 

       indices[whichString] = f.characters.index(after: cursor) 

       if whichString == 0  { toMatch = f[cursor] } 
       if toMatch != f[cursor] { break outerLoop  } 
      } 

      commonPrefix.append(toMatch) 
    } 

    return commonPrefix 
} 

Что интересно отметить:

1. выполняется в O^2 или O (nxm), где n - количество строк и m - длина самого короткого.
2. использует тип данных String.Index и, следовательно, имеет дело с Grapheme Clusters, который представляет тип Character.

И учитывая функцию мне нужно написать в первую очередь:

/// Takes an array of Strings representing file system objects absolute 
/// paths and turn it into a new array with the minimum number of common 
/// ancestors, possibly pushing the root of the tree as many level downwards 
/// as necessary 
/// 
/// In other words, we compute the longest common prefix and remove it 

func reify(fullPaths:[String]) -> [String] { 

    let lcp = longestCommonPrefix(fullPaths) 

    return fullPaths.map { 
     return $0[lcp.endIndex ..< $0.endIndex] 
    } 
} 

здесь минимальный тестовый модуль:

func testReifySimple() { 
    let samplePaths:[String] = [ 
     "/root/some/file" 
    , "/root/some/other/file" 
    , "/root/another/file" 
    , "/root/direct.file" 
    ] 

    let expectedPaths:[String] = [ 
     "some/file" 
    , "some/other/file" 
    , "another/file" 
    , "direct.file" 
    ] 

    let reified = PathUtilities().reify(samplePaths) 

    for (index, expected) in expectedPaths.enumerate(){ 
     XCTAssert(expected == reified[index], "failed match, \(expected) != \(reified[index])") 
    } 
}