如何实现字符串匹配算法？

字符串匹配算法是在一个文本字符串中查找与给定模式字符串匹配的第一个位置。常见的算法有:

1. 暴力匹配:

public int indexOf(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j))
                break;
        }
        if (j == m) return i;
    }
    return -1;
}

时间复杂度O(nm),空间复杂度O(1)。

2. KMP算法:利用模式字符串的样式,提高匹配效率。

public int indexOf(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] next = getNextArray(pattern);

    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }

        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }

        if (j == m) return i - m + 1;
    }

    return -1; 
}

private int[] getNextArray(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];

    next[0] = -1;
    int k = -1;
    int j = 0;

    while (j < m - 1) {
        if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
            next[++j] = ++k; 
        } else {
            k = next[k];
        }
    }

    return next;
}

时间复杂度O(n),空间复杂度O(m)。

所以,字符串匹配算法的关键是:

1. 暴力匹配:简单但效率低,时间复杂度高。
2. KMP算法:利用模式字符串本身的特征,匹配效率高,时间复杂度低。
3. KMP算法需要构建next数组,代表模式串中前缀与后缀的最长公共子序列长度。