Эффективный алгоритм поиска строк?

Question

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

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

// return true if a is a substring of b 
def is_sub(a: String, b: String) : Boolean = { 
    for(i <- 0 until b.length-a.length) { // O(n-m) 
    if(a.hashCode == b.substring(i,a.length+i).hashCode) return true // O(1) + O(1) + O(1) 
    } 
    return false 
} 

Во-первых, кто-то может проверить мою работу и убедитесь, что я прав. Я склонен к глупым ошибкам. Во-вторых, можете ли вы проверить, насколько точны мои временные сложности. Предполагая, что первые 2 - это то, что я думаю, почему они не упомянуты на странице wikipedia для string searching algorithms? Теоретически это должно быть O (n-m) без необходимого пространства для предварительной обработки.

Где я напортачил свой анализ этой проблемы?

Answer 1

Неправильно указан код, который вы опубликовали. Если две строки равны, то их хэш-коды должны быть одинаковыми, но обратное значение не обязательно верно. Можно найти пары строк, которые являются разными строками, но имеют одинаковый хеш-код. Следовательно, ваша функция может вернуть неверный ответ, если вы найдете подстроку с тем же хеш-кодом, что и строка для поиска.

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

Однако то, что вы делаете, тесно связано с Rabin-Karp string searching algorithm, которое действительно основано на хеширующих строках. Чтобы избежать выполнения O (n) работы на каждой итерации, алгоритм использует скользящую хеш-функцию, которая может быть легко обновлена ​​с одной подстроки на следующую по времени O (1). Он также имеет дополнительную проверку, чтобы, если текущий хэш-код соответствует хеш-коду для подстроки, алгоритм фактически проверяет каждый символ, чтобы убедиться, что они совпадают. Этот алгоритм берет время O (mn) в худшем случае, но в среднем случае намного, намного быстрее (время O (m + n)).

Надеюсь, это поможет!

Answer 2

Ваш алгоритм по-прежнему равен O (n m).

Пусть m - длина рисунка, n - длина искомой строки.

В каждой из (n - m) позиций в искомой строке вы создаете подстроку и вычисляете ее хэш-код. Для каждого из них требуется итерация над m символами.

Сложность зависит не только от кода, который вы написали, но и от кода, который вы назвали.