Алгоритм KMP медленнее, чем брутфорс - PullRequest
Новая
       31

Алгоритм KMP медленнее, чем брутфорс

0 голосов
/ 22 апреля 2020

Я практиковал проблему реализации функции strstr (). И первое, что пришло мне в голову, когда я увидел вопрос, было: «Эй, это KMP!». Но удивительно, я обнаружил, что использование грубой силы было быстрее, чем KMP. Кто-нибудь может объяснить почему? Вот мое грубое решение: 

public int strStr(String haystack, String needle) {
   if(needle.equals(""))
       return 0;
    int len1=haystack.length();
    int len2=needle.length();
    for(int i=0;i<=len1-len2;i++)
    {
        if(haystack.charAt(i)==needle.charAt(0) && haystack.substring(i,i+len2).equals(needle))
            return i;
    }
    return -1;
}

Вот мое решение KMP: 

class Solution {
public int strStr(String haystack, String needle) {
   if(needle.equals(""))
       return 0;
    int len1=haystack.length();
    int len2=needle.length();
    if(len2>len1)
        return -1;
    int lps[]=preprocess(needle,len2);
    int i=0,j=0;
    int ind=-1;
    while(i<len1 && j<len2)
    {
        if(haystack.charAt(i)==needle.charAt(j))
        {
            i++;j++;
        }
        else
        {
            if(j>0)
                j=lps[j-1];
            else
                i++;
        }
    }
    return j==len2?i-len2:-1;
}
public int[] preprocess(String needle,int len)
{
    int i=1,j=0,lps[]= new int[len];
    while(i<len)
    {
        if(needle.charAt(i)==needle.charAt(j))
        {
            lps[i++]=++j;
        }
        else
        {
            if(j>0)
                j=lps[j-1];
            else
                i++;
        }
    }
    return lps;
}

} Кто-нибудь может объяснить, почему это происходит? Разве KMP не должен быть быстрее, чем брутфорс? А если нет, можете ли вы объяснить, когда использовать KMP? Спасибо всем, кто пытается помочь:).

...