KMP 算法详解 | Yuhi's Blog

[utterances-bot]

KMP 算法详解 | Yuhi's Blog

KMP 真是优雅的算法呢

https://yuhi.xyz/post/KMP-%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/

[hbsun2113]

感谢分享，但我觉得索引可以直接从0开始，这样更方便理解？ `int strStr(string haystack, string pattern) { int m=haystack.size(); int n=pattern.size(); vector lps(n, 0);

    // build the lps
    for(int i=1, j=0;i<n;i++)
    {
        while(j && pattern[i]!=pattern[j]) j=lps[j-1];
        if(pattern[i]==pattern[j]) j++;
        lps[i]=j;
    }

    // find match
    for(int i=0, j=0;i<m;i++)
    {
        while(j && haystack[i]!=pattern[j]) j=lps[j-1];
        if(haystack[i]==pattern[j]) j++;
        if(j==n)
        {
            return i-n+1;
        }
    }

    return -1;
}`

[hbsun2113]

    int strStr(string haystack, string pattern)
    {
        int m=haystack.size();
        int n=pattern.size();
        vector<int> lps(n, 0);

        // build the lps
        // lps[0]肯定是0，所以i从1开始
        for(int i=1, j=0;i<n;i++)
        {
            while(j && pattern[i]!=pattern[j]) j=lps[j-1];
            if(pattern[i]==pattern[j]) j++;
            lps[i]=j;
        }

        // find match
        for(int i=0, j=0;i<m;i++)
        {
            while(j && haystack[i]!=pattern[j]) j=lps[j-1];
            if(haystack[i]==pattern[j]) j++;
            if(j==n)
            {
                return i-n+1;
            }
        }

        return -1;
    }