Алгоритм подстроки O (n) - PullRequest
Новая
       38

Алгоритм подстроки O (n)

1 голос
/ 27 января 2020

, поэтому я исследовал алгоритмы поиска подстрок и обнаружил, что большинству алгоритмов, таким как алгоритм kmp и rabin-karp, требуется дополнительная сложность времени для предварительной обработки перед выполнением некоторого сопоставления строк. есть ли польза от этого? и почему бы им просто не перейти сразу к совпадению строк, чтобы сложность времени big-O не упала до O (m + n)? Я попытался создать алгоритм подстроки, который я считаю O (n) (пожалуйста, исправьте меня, если я ошибаюсь), просто пропустив время предварительной обработки. И мне интересно, почему люди не делают этого таким образом, пожалуйста, обратитесь к приведенному ниже коду C. 

int search(char hay[], char needle[], int hayLen, int needleLen){
    int found;
    int i = 0;

    while (i < (hayLen - needleLen + 1)){
        if (hay[i] == needle[0]){
            found = 1;
            for (int j=0; j<needleLen; j++){
                if (hay[i] != needle[j]){
                    found = 0;
                    break;
                }
                i++;
            }
            if (found)
                return i - needleLen;
        }
        else
            i++;
    }
    return -1;
}

edit:

удалил функцию strlen, чтобы избежать любые нежелательные временные сложности

Ответы [ 3 ]

8 голосов
/ 27 января 2020

Честно говоря не страшный вопрос. Я думаю, что большинство из нас пытались создать подобное решение, когда пытались создать алгоритм поиска строк, прежде чем открывать KMP. Ответ в том, что этот жадный алгоритм не работает - он никогда не возвращается в i. Вы можете подумать «ага! это начало иглы! » и двигайтесь вперед, пока не обнаружите «э-э-э! это не вся игла! » В этом алгоритме мы продвигаемся только вперед, продолжая искать начало стрелки. Однако начало настоящей иглы, возможно, было тем, что, по вашему мнению, было средним символом при попытке жадно сопоставить как можно большую часть иглы.

Например, aab и aaab. Только в третьем a вы понимаете: «э-э-э, это не стрелка в конце концов», и после этого начинается тщательный алгоритм O (nm) со второй позиции, но ваш алгоритм просто движется вперед, и никогда не понимает aab, который начинается на второй позиции. KMP решает эту проблему, отмечая, какие части иглы в середине также могут быть потенциальными отправными точками для иглы.

5 голосов
/ 27 января 2020

Ваш текущий код O (n), но ...

Ваш код не работает!

Попробуйте: 

int main()
{
    char a[] = "aaaab";
    char b[] = "aaab";
    if (search(a, b, strlen(a), strlen(b)) != -1) 
        printf("OK\n"); 
    else 
        printf("FAIL\n");
    return 0;
}

Очевидно b можно найти в a, но ваш код говорит, что его нет.

Проблема в том, что вы всегда увеличиваете i. Делая это, вы получаете O (n), но это также приводит к сбою кода.

0 голосов
/ 27 января 2020

удалил функцию strlen, чтобы избежать нежелательных временных сложностей

Вы удалили вызовы strlen, но теперь длина строки должна быть передана в функцию : 

int search(char hay[], char needle[], int hayLen, int needleLen)

Итак ... как изменяется сложность поиска по всей подстроке при увеличении размера needle? В конце концов, независимо от того, рассчитываете ли вы длину внутри функции или за ее пределами, это все же необходимо сделать. O(m+n) означает, что сложность зависит от длины как needle, так и haystack.

Чтобы довести точку до крайности, вы можете написать функцию O (1) search, просто добавив параметр, который указывает местоположение needle в haystack.

...