AC KMP solution


  • 3
    D
    class Solution {
    public:
        
        int strStr(char *haystack, char *needle) {
            int n = strlen(haystack);
            int m = strlen(needle);
            if (m == 0) return 0;
            
            /*Counting prefix function for needle*/      
            int *p = new int[m];
            for (int i = 0; i < m; i++)
                p[i] = 0;
                
            for (int i = 1; i < m; i++) {
                p[i] = p[i - 1];
                while (p[i] > 0 && needle[p[i]] != needle[i])
                    p[i] = p[p[i] - 1];
                if (needle[p[i]] == needle[i])
                    p[i]++;
            }
            /***********************************/
            
            /*KMP algo*/
            int pre = 0;
            for (int i = 0; i < n; i++) {
                while (pre > 0 && needle[pre] != haystack[i])
                    pre = p[pre - 1];
                if (needle[pre] == haystack[i]) pre++;
                if (pre == m) {
                    return i - pre + 1;
                }
            }
            /*********/
            
            return -1;
        }
    };

  • 0
    H

    where is “delete”?


  • 0
    L

    LOL, sharp eyes, a minor mistake~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.