Как найти максимальный префикс - Исправление недочетов и поиск решений вместе с Examum.ru

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Problem Statement: Given a set of strings, find the longest common prefix.
Examples:

Input: {"geeksforgeeks", "geeks", "geek", "geezer"}
Output: "gee"

Input: {"apple", "ape", "april"}
Output: "ap"

The longest common prefix for an array of strings is the common prefix between 2 most dissimilar strings. For example, in the given array {“apple”, “ape”, “zebra”}, there is no common prefix because the 2 most dissimilar strings of the array “ape” and “zebra” do not share any starting characters.
We have discussed five different approaches in below posts.

Word by Word Matching
Character by Character Matching
Divide and Conquer
Binary Search.
Using Trie)

In this post a new method based on sorting is discussed. The idea is to sort the array of strings and find the common prefix of the first and last string of the sorted array.

Python 3

def longestCommonPrefix( a):

size = len(a)

if (size == 0):

return ""

if (size == 1):

return a[0]

a.sort()

end = min(len(a[0]), len(a[size - 1]))

i = 0

while (i < end and

a[0][i] == a[size - 1][i]):

i += 1

pre = a[0][0: i]

return pre

if __name__ == "__main__":

input = ["geeksforgeeks", "geeks",

"geek", "geezer"]

print("The longest Common Prefix is :" ,

longestCommonPrefix(input))

Output

The longest Common Prefix is : gee

Time Complexity: O(MAX * n * log n ) where n is the number of strings in the array and MAX is maximum number of characters in any string. Please note that comparison of two strings would take at most O(MAX) time and for sorting n strings, we would need O(MAX * n * log n ) time.

Space Complexity: O(1) as no extra space has been used.

Please refer complete article on Longest Common Prefix using Sorting for more details!

Last Updated :
24 Mar, 2023

Like Article

Save Article

Источник

#статьи

24 авг 2022
0

Задача: ищем самый длинный общий префикс у элементов массива строк

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем общий префикс в массиве строк.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Необходимо написать функцию, которая находит самый длинный общий префикс среди элементов массива строк. Если такого префикса нет, программа должна вернуть пустую строку.


Ввод: strs = ["flower", "flow", "flight"]
Вывод: "fl"


Ввод: strs = ["dog", "racecar", "car"]
Вывод: ""
// Пояснение: у этих строк нет общего префикса.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из Telegram-канала Сергея Cracking code interview.

Решение

Чтобы решить эту задачу, мы будем использовать принцип «скользящего окна». Его суть в том, что мы берём две строки и начинаем посимвольно сравнивать их, как бы смотря на них через окно.

Для нашей задачи это самый простой и очевидный метод решения. Мы возьмём два указателя — начала и конца — и будем перемещать их в зависимости от условий: нашли или не нашли одинаковую последовательность символов.

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

Полный алгоритм такой:

Сначала проверяем размер массива: если массив пустой, то и общий префикс — пустая строка. А если в массиве только один элемент, то он и будет общим префиксом.
В остальных случаях берём первую строку массива и принимаем её за самый длинный общий префикс.
Ставим два указателя: один будет следить за индексом последнего символа, который совпал с нашим общим префиксом, а второй будет перемещаться по строкам посимвольно.
Перебираем элементы массива, начиная со второго — сравниваем символы в этом элементе с символами общего префикса. Если символы равны, увеличиваем индекс общего префикса на один, если нет — просто идём дальше.
После проверки очередной строки массива отрезаем от общего префикса лишние символы — по индексу, который сохранён в нашем указателе.

Вот как этот алгоритм будет реализован на Java:


public String longestCommonPrefix(String[] strs) {
    if(strs.length == 0){
      return "";
    }
    if (strs.length == 1){
      return strs[0];
    }
     
    String rez = strs[0];
    for(int i = 1; i < strs.length; i ++){
      String cur = strs[i];
      int reader = 0;
      int lastCommon = 0;
      while(reader < rez.length() && reader < cur.length()){
        if(rez.charAt(reader) == cur.charAt(reader)){
          lastCommon ++;
        } else {
          break;
        }
        reader++;
      }
      rez = rez.substring(0, lastCommon);
    }
    return rez;
  }

Результаты

Временная сложность: O(n) — так как мы перебирали все элементы массива.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти (максимальный размер памяти — длина первого слова в массиве).

Научитесь: Профессия Java-разработчик
Узнать больше

Источник

Напишите эффективный алгоритм для поиска самого длинного общего префикса (LCP) между заданным набором строк.

Например,

Input: technique, technician, technology, technical
Output: The longest common prefix is techn

Input: techie delight, tech, techie, technology, technical
Output: The longest common prefix is tech

Потренируйтесь в этой проблеме

Простое решение состоит в том, чтобы рассмотреть каждую строку и вычислить ее самый длинный общий префикс с самым длинным общим префиксом строк, обработанных до сих пор. Временная сложность этого решения O(N.M), куда N это общее количество слов и M максимальная длина слова.

Это показано ниже на C++, Java и Python:

C++

#include <iostream>

#include <vector>

#include <string>

using namespace std;

// Функция для поиска самого длинного общего префикса между двумя строками

string LCP(string X, string Y)

{

int i = 0, j = 0;

while (i < X.length() && j < Y.length())

{

if (X[i] != Y[j]) {

break;

}

i++, j++;

}

return X.substr(0, i);

}

// Функция для поиска самого длинного общего префикса (LCP) между заданным набором строк

string findLCP(vector<string> const &words)

{

string prefix = words[0];

for (string s: words) {

prefix = LCP(prefix, s);

}

return prefix;

}

int main()

{

vector<string> words { «techie delight», «tech», «techie»,

«technology», «technical» };

cout << «The longest common prefix is « << findLCP(words);

return 0;

}

Скачать Выполнить код

результат:

The longest common prefix is tech

Java

import java.util.Arrays;

import java.util.List;

class Main

{

// Функция для поиска самого длинного общего префикса между двумя строками

public static String LCP(String X, String Y)

{

int i = 0, j = 0;

while (i < X.length() && j < Y.length())

{

if (X.charAt(i) != Y.charAt(j)) {

break;

}

i++; j++;

}

return X.substring(0, i);

}

// Функция для поиска самого длинного общего префикса (LCP) между заданным набором строк

public static String findLCP(List<String> words)

{

String prefix = words.get(0);

for (String s: words) {

prefix = LCP(prefix, s);

}

return prefix;

}

public static void main(String[] args)

{

List<String> words = Arrays.asList(«techie delight», «tech», «techie»,

«technology», «technical»);

System.out.println(«The longest common prefix is « + findLCP(words));

}

Скачать Выполнить код

результат:

The longest common prefix is tech

Python

# Функция поиска самого длинного общего префикса между двумя строками

def LCP(X, Y):

i = j = 0

while i < len(X) and j < len(Y):

if X[i] != Y[j]:

break

i = i + 1

j = j + 1

return X[:i]

# Функция поиска самого длинного общего префикса (LCP) между заданным набором строк

def findLCP(words):

prefix = words[0]

for s in words:

prefix = LCP(prefix, s)

return prefix

if __name__ == ‘__main__’:

words = [‘techie delight’, ‘tech’, ‘techie’, ‘technology’, ‘technical’]

print(‘The longest common prefix is’, findLCP(words))

Скачать Выполнить код

результат:

The longest common prefix is tech

Мы также можем использовать Разделяй и властвуй метод нахождения самого длинного общего префикса (LCP). Как и во всех алгоритмах «разделяй и властвуй», идея состоит в том, чтобы разделить строки на два меньших набора и затем рекурсивно обработать эти наборы. Это похоже на Сортировка слиянием рутина, за исключением того, что мы находим LCP двух половин вместо слияния обеих половин.

C++

#include <iostream>

#include <vector>

#include <string>

using namespace std;

// Функция для поиска самого длинного общего префикса между двумя строками

string LCP(string X, string Y)

{

int i = 0, j = 0;

while (i < X.length() && j < Y.length())

{

if (X[i] != Y[j]) {

break;

}

i++, j++;

}

return X.substr(0, i);

}

// Рекурсивная функция для поиска самого длинного общего префикса (LCP) между

// данный набор строк

string findLCP(vector<string> const &words, int low, int high)

{

// базовый случай: если `low` больше, чем `high`, вернуть пустую строку

if (low > high) {

return string(«»);

}

// базовый случай: если `low` равно `high`, вернуть текущую строку

if (low == high) {

return words[low];

}

// найти середину индекса

int mid = (low + high) / 2;

// разбиваем проблему на подзадачи и повторяем для каждой подзадачи

string X = findLCP(words, low, mid);

string Y = findLCP(words, mid + 1, high);

// вернуть самый длинный общий префикс строк `X` и `Y`

return LCP(X, Y);

}

int main()

{

vector<string> words = { «techie delight», «tech», «techie»,

«technology», «technical» };

cout << «The longest common prefix is « << findLCP(words, 0, words.size() — 1);

return 0;

}

Скачать Выполнить код

результат:

The longest common prefix is tech

Java

import java.util.Arrays;

import java.util.List;

class Main

{

// Функция для поиска самого длинного общего префикса между двумя строками

public static String LCP(String X, String Y)

{

int i = 0, j = 0;

while (i < X.length() && j < Y.length())

{

if (X.charAt(i) != Y.charAt(j)) {

break;

}

i++; j++;

}

return X.substring(0, i);

}

// Рекурсивная функция для поиска самого длинного общего префикса (LCP) между

// данный набор строк

public static String findLCP(List<String> words, int low, int high)

{

// базовый случай: если `low` больше, чем `high`, вернуть пустую строку

if (low > high) {

return «»;

}

// базовый случай: если `low` равно `high`, вернуть текущую строку

if (low == high) {

return words.get(low);

}

// найти середину индекса

int mid = (low + high) / 2;

// разбиваем проблему на подзадачи и повторяем для каждой подзадачи

String X = findLCP(words, low, mid);

String Y = findLCP(words, mid + 1, high);

// вернуть самый длинный общий префикс строк `X` и `Y`

return LCP(X, Y);

}

public static void main(String[] args)

{

List<String> words = Arrays.asList(«techie delight», «tech», «techie»,

«technology», «technical»);

System.out.println(«The longest common prefix is « +

findLCP(words, 0, words.size() — 1));

}

Скачать Выполнить код

результат:

The longest common prefix is tech

Python

# Функция поиска самого длинного общего префикса между двумя строками

def LCP(X, Y):

i = j = 0

while i < len(X) and j < len(Y):

if X[i] != Y[j]:

break

i = i + 1

j = j + 1

return X[:i]

# Рекурсивная функция для поиска самого длинного общего префикса (LCP) между

# данный набор строк

def findLCP(words, low, high):

# Базовый случай: если `low` больше, чем `high`, вернуть пустую строку

if low > high:

return »

# Базовый случай: если `low` равен `high`, вернуть текущую строку.

if low == high:

return words[low]

# найти средний индекс

mid = (low + high) // 2

# разбивает проблему на подзадачи и повторяет каждую подзадачу.

X = findLCP(words, low, mid)

Y = findLCP(words, mid + 1, high)

# возвращает самый длинный общий префикс строк `X` и `Y`

return LCP(X, Y)

if __name__ == ‘__main__’:

words = [‘techie delight’, ‘tech’, ‘techie’, ‘technology’, ‘technical’]

print(‘The longest common prefix is’, findLCP(words, 0, len(words) — 1))

Скачать Выполнить код

результат:

The longest common prefix is tech

Временная сложность приведенного выше решения равна O(N.M), куда N это общее количество слов и M максимальная длина слова. Используемое вспомогательное пространство O(M.log(N)) для стека вызовов.

Также см:

Самый длинный общий префикс в заданном наборе строк (с использованием Trie)

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования

Источник

Определение. Префикс-функцией от строки $s$ называется массив $p$, где $p_i$ равно длине самого большого префикса строки $s_0 s_1 s_2 ldots s_i$, который также является и суффиксом $i$-того префика (не считая весь $i$-й префикс).

Например, самый большой префикс, который равен суффиксу для строки «aataataa» — это «aataa»; префикс-функция для этой строки равна $[0, 1, 0, 1, 2, 3, 4, 5]$.

vector<int> slow_prefix_function(string s) {
    int n = (int) s.size();
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++)
        for (int len = 1; len <= i; len++)
            // если префикс длины len равен суффиксу длины len
            if (s.substr(0, len) == s.substr(i - len + 1, len))
                p[i] = len;
    return p;
}

Этот алгоритм пока что работает за $O(n^3)$, но позже мы его ускорим.

#Как это поможет решить исходную задачу?

Давайте пока поверим, что мы умеем считать префикс-функцию за линейное от размера строки, и научимся с помощью нее искать подстроку в строке.

Соединим подстроки $s$ и $t$ каким-нибудь символом, который не встречается ни там, ни там — обозначим пусть этот символ #. Посмотрим на префикс-функцию получившейся строки s#t.

string s = "choose";
string t =
    "choose life. choose a job. choose a career. choose a family. choose a fu...";

cout << s + "#" + t << endl;
cout << slow_prefix_function(s + "#" + t) << endl;

choose#choose life. choose a job. choose a career. choose a family. choose a fu...
0000000123456000000012345600000000123456000100000001234560000000000012345600000000

Видно, что все места, где значения равны 6 (длине $s$) — это концы вхождений $s$ в текст $t$.

Такой алгоритм (посчитать префикс-функцию от s#t и посмотреть, в каких позициях она равна $|s|$) называется алгоритмом Кнута-Морриса-Пратта.

#Как её быстро считать

Рассмотрим ещё несколько примеров префикс-функций и попытаемся найти закономерности:

aaaaa
01234

abcdef
000000

abacabadava
00101230101

Можно заметить следующую особенность: $p_{i+1}$ максимум на единицу превосходит $p_i$.

Доказательство. Если есть префикс, равный суффиксу строки $s_{:i+1}$, длины $p_{i+1}$, то, отбросив последний символ, можно получить правильный суффикс для строки $s_{:i}$, длина которого будет ровно на единицу меньше.

Попытаемся решить задачу с помощью динамики: найдём формулу для $p_i$ через предыдущие значения.

Заметим, что $p_{i+1} = p_i + 1$ в том и только том случае, когда $s_{p_i} =s_{i+1}$. В этом случае мы можем просто обновить $p_{i+1}$ и пойти дальше.

Например, в строке $underbrace{aabaa}toverbrace{aabaa}$ выделен максимальный префикс, равный суффиксу: $p_{10} = 5$. Если следующий символ равен будет равен $t$, то $p_{11} = p_{10} + 1 = 6$.

Но что происходит, когда $s_{p_i}neq s_{i+1}$? Пусть следующий символ в этом же примере равен не $t$, а $b$.

$implies$ Длина префикса, равного суффиксу новой строки, будет точно меньше 5.
$implies$ Помимо того, что искомый новый супрефикс является суффиксом «aabaab», он ещё является префиксом подстроки «aabaa».
$implies$ Значит, следующий кандидат на проверку — это значение префикс-функции от «aabaa», то есть $p_4 = 2$, которое мы уже посчитали.
$implies$ Если $s_2 = s_{11}$ (т. е. новый символ совпадает с идущим после префикса-кандидата), то $p_{11} = p_2 + 1 = 2 + 1 = 3$.

В данном случае это действительно так (нужный префикс — «aab»). Но что делать, если, в общем случае, $p_{i+1} neq p_{p_i+1}$? Тогда мы проводим такое же рассуждение и получаем нового кандидата, меньшей длины — $p_{p_{p_i}}$. Если и этот не подошел — аналогично проверяем меньшего, пока этот индекс не станет нулевым.

vector<int> prefix_function(string s) {
    int n = (int) s.size();
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++) {
        // префикс функция точно не больше этого значения + 1
        int cur = p[i - 1];
        // уменьшаем cur значение, пока новый символ не сматчится
        while (s[i] != s[cur] && cur > 0)
            cur = p[cur - 1];
        // здесь либо s[i] == s[cur], либо cur == 0
        if (s[i] == s[cur])
            p[i] = cur + 1;
    }
    return p;
}

Асимптотика. В худшем случае этот while может работать $O(n)$ раз за одну итерацию, но в среднем каждый while работает за $O(1)$.

Префикс-функция каждый шаг возрастает максимум на единицу и после каждой итерации while уменьшается хотя бы на единицу. Значит, суммарно операций будет не более $O(n)$.

Источник

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

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

Полиномиальный хеш как раз позволяет найти сначала хеш всей строки, а потом за O(1) находить хеш подстроки, что удобно для сравнения этих самых подстрок.

Но есть проблема: мой бинарный поиск напонятно по каким причинам находит неправильную длину префикса и я никак не могу это отдебагать.

В чём проблема?

Поиск префикса:

int d(string &a, string &b) {

    StrHash ha(a), hb(b);
    int mid, l = 0, r = min(a.size(), b.size()) - 1;

    while(l < r) {
        mid = (l + r) / 2;
        if(ha.get(0, mid) == hb.get(0, mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    int common;
    ///А тут мы проверяем, нашли мы префикс или нет.
    if(ha.get(0, l) == hb.get(0, l)) common = l + 1;
    else common = 0;

    return common;
}

Тест с багом, находит ответ 0:

s1 = 'aaaaa'
s2 = 'ab'

Источник