leetcode28. 找出字符串中第一个匹配项的下标_简单KMP

 28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

模仿：algorithm-journey/src/class100/Code01_KMP.java at main · algorithmzuo/algorithm-journey · GitHub

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void getNext(char *s, int m, int *next) {
    if (m == 1) {
        next[0] = -1;
        return;
    }
    next[0] = -1;
    next[1] = 0;
    int i = 2, cn = 0;
    while (i < m) {
        if (s[i - 1] == s[cn]) {
            next[i++] = ++cn;
        } else if (cn > 0) {
            cn = next[cn];
        } else {
            next[i++] = 0;
        }
    }
}


int kmp(char *s1, char *s2) {
    int n = strlen(s1), m = strlen(s2);
    int x = 0, y = 0;
    int *next = (int *)malloc(m * sizeof(int));
    getNext(s2, m, next);
    while (x < n && y < m) {
        if (s1[x] == s2[y]) {
            x++;
            y++;
        } else if (y == 0) {
            x++;
        } else {
            y = next[y];
        }
    }
    free(next);
    return y == m ? x - y : -1;
}

int strStr(char *haystack, char *needle) {
    return kmp(haystack, needle);
}
   

 官方题解：

C++

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

C：

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    if (m == 0) {
        return 0;
    }
    int pi[m];
    pi[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (needle[i] == needle[j]) {
            j++;
        }
        pi[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

待定