Вопрос:
Указанная n строка максимальной длины m. Как мы можем найти самый длинный общий префикс, совместно используемый по меньшей мере двумя строками среди них?
Пример: [‘flower’, ‘flow’, ‘hello’, ‘fleet’]
Ответ: fl
Я думал построить Trie для всей строки, а затем проверил самый глубокий node (наиболее длинный), который разветвляется на две подстроки (удовлетворяет общности). Это берет O (n * m) время и пространство. Есть ли лучший способ сделать это
Ответ №1
Существует O(|S|*n) решение этой проблемы с использованием 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 than 1 «edge». (3) the path from the root to the node you found at (2) is the longest common prefix.
Нет более быстрого решения, чем оно [с точки зрения больших цифр O], в худшем случае все ваши строки идентичны – и вам нужно прочитать все из них, чтобы узнать это.
Ответ №2
Зачем использовать 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); } Ответ №3
Я бы отсортировал их, что вы можете сделать в n lg n времени. Тогда любые строки с общими префиксами будут расположены рядом друг с другом. Фактически, вы должны иметь возможность указывать указатель на индекс, который вы сейчас просматриваете, и работать с ним довольно быстро.
Ответ №4
Как совершенно другой ответ из моего другого ответа…
Вы можете с одним проходом записать каждую строку на основе ее первой буквы.
С помощью другого прохода вы можете сортировать каждое ведро на основании его второго позже. (Это называется сортировка radix, которая O(n*m) и O(n) с каждым проходом.) Это дает вам базовый префикс в 2.
Вы можете безопасно удалить из своего набора данных любые элементы, у которых нет префикса из 2.
Вы можете продолжить сортировку radix, удалив элементы без общего префикса p, поскольку p приближается к m.
Это даст вам то же самое время O(n*m), что и trie-подход, но всегда будет быстрее, чем trie, поскольку trie должен смотреть на каждый символ в каждой строке (когда он входит в структуру), тогда как этот подход только гарантированно будет смотреть на 2 символа на строку, после чего она отбирает большую часть набора данных.
В худшем случае все равно, что каждая строка идентична, поэтому она разделяет одну и ту же большую нотацию O, но будет быстрее во всех случаях, так как гарантируется использование меньших сравнений, поскольку в любом “не худшем случае” там это символы, которые никогда не нужно посещать.
Ответ №5public 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); } Ответ №6
Бывает, что сортировка ведра (сортировка по ради), описанная corsiKa, может быть расширена так, что все строки в конечном итоге помещаются отдельно в ведро, и в этот момент известно, что LCP для такой одинокой строки. Кроме того, известно также разрушение каждой строки; он длиннее, чем LCP. Сортировка ковша деформирует конструкцию массива суффиксов, но только частично. Те сравнения, которые не выполняются (как описано corsiKa), действительно представляют те части суффиксных строк, которые не добавлены в массив суффикса. Наконец, этот метод позволяет определять не только LCP и shustrings, но также легко найти те подпоследовательности, которые отсутствуют в строке.
Ответ №7
Так как мир, очевидно, попросил ответа в Свифте, вот мой;)
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:
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 }
Что интересно отметить:
- это выполняется в O ^ 2, или O (n x m), где n – число строк и m
это длина самого короткого. - используется тип данных 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] } }
здесь минимальный unit test:
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])») } } Ответ №8
Возможно, более интуитивное решение. Направьте уже найденный префикс из предыдущей итерации в качестве входной строки на вход оставшейся или следующей строки. [[[w1, w2], w3], w4]… so on], где [] – предположительно LCP из двух строк.
public String findPrefixBetweenTwo(String A, String B){ String ans = «»; for (int i = 0, j = 0; i < A.length() && j < B.length(); i++, j++){ if (A.charAt(i) != B.charAt(j)){ return i > 0 ? A.substring(0, i) : «»; } } // Either of the string is prefix of another one OR they are same. return (A.length() > B.length()) ? B.substring(0, B.length()) : A.substring(0, A.length()); } public String longestCommonPrefix(ArrayList<String> A) { if (A.size() == 1) return A.get(0); String prefix = A.get(0); for (int i = 1; i < A.size(); i++){ prefix = findPrefixBetweenTwo(prefix, A.get(i)); // chain the earlier prefix } return prefix; }
