java-字符串处理算法

Java的字符串处理算法

1. KMP算法（Knuth-Morris-Pratt Algorithm）

定义：
KMP算法是一种用于字符串搜索的高效算法，它可以在O(n+m)的时间复杂度内找到模式串在文本串中的第一次出现的位置，其中n是文本串的长度，m是模式串的长度。

原理：
KMP算法的核心是构建一个部分匹配表（也称为前缀函数或失败函数），用于在不匹配时避免从头开始搜索模式串。

Java实现示例：

public class KMP {
    public static void search(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int i = 0; // index for text
        int j = 0; // index for pattern
        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                System.out.println("Found pattern at index " + (i - j));
                j = lps[j - 1];
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    // Build LPS array
    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // length of the previous longest prefix suffix
        int i = 1;
        lps[0] = 0; // lps[0] is always 0
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else { // (pat.charAt(i) != pat.charAt(len))
                if (len != 0) {
                    len = lps[len - 1];
                } else { // if (len == 0)
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        search(text, pattern);
    }
}

2. Rabin-Karp算法

定义：
Rabin-Karp算法是一种用于字符串搜索的算法，它利用了哈希函数来快速筛选出可能匹配的子串，然后进行详细的比较。

原理：
算法通过计算模式串和文本串中每个可能的子串的哈希值来快速找到匹配的子串。

Java实现示例：

import java.util.HashMap;
import java.util.Map;

public class RabinKarp {
    public static int search(String text, String pattern) {
        long patternHash = hash(pattern);
        long currentHash = hash(text.substring(0, pattern.length()));
        int modulus = (int)1e9 + 9;
        for (int i = 0; i <= text.length() - pattern.length(); i++) {
            if (currentHash == patternHash) {
                if (i <= text.length() - pattern.length()) {
                    // Check if characters match
                    int j;
                    for (j = 0; j < pattern.length(); j++) {
                        if (text.charAt(i + j) != pattern.charAt(j)) {
                            break;
                        }
                    }
                    if (j == pattern.length()) {
                        return i;
                    }
                }
            }
            if (i < text.length() - pattern.length()) {
                currentHash = (currentHash - (text.charAt(i) * pow(256, pattern.length() - 1, modulus))) * 256 + text.charAt(i + pattern.length());
                currentHash = (currentHash + modulus) % modulus;
            }
        }
        return -1;
    }

    private static long hash(String key) {
        long hash = 0;
        for (int i = 0; i < key.length(); i++) {
            hash += key.charAt(i);
            hash %= 1000000007; // Using prime number as modulus
        }
        for (int i = 0; i < key.length() - 1; i++) {
            hash = (hash * 256) % 1000000007;
        }
        return hash;
    }

    private static long pow(int x, int n, int mod) {
        long res = 1;
        x = x % mod;
        while (n > 0) {
            if (n % 2 == 1) {
                res = (res * x) % mod;
            }
            x = (x * x) % mod;
            n = n / 2;
        }
        return res;
    }

    public static void main(String[] args) {
        String text = "hello world";
        String pattern = "world";
        System.out.println(search(text, pattern));
    }
}

3. Z算法（Z-Algorithm）

定义：
Z算法是一种字符串搜索算法，它可以在O(n+m)的时间复杂度内找到模式串在文本串中的所有出现位置。

原理：
算法通过比较模式串和文本串的字符来构建一个Z数组，该数组表示模式串中每个位置的最长相同前缀和后缀的长度。

Java实现示例：

public class ZAlgorithm {
    public static int[] computeZArray(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] z = new int[n];
        int j = 0;
        for (int i = 1; i < n; i++) {
            if (i > j) {
                j = 0;
                while (j < m && pattern.charAt(j) == text.charAt(i + j)) {
                    j++;
                }
                z[i] = j;
                if (j > 0) {
                    j--;
                }
            }
            while (n - i < j && j > 0) {
                z[i + n - j] = j;
                j--;
            }
        }
        return z;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int[] zArray = computeZArray(text, pattern);
        for (int i = 0; i < zArray.length; i++) {
            System.out.println("z[" + i + "]: " + zArray[i]);
        }
    }
}

4. 后缀数组（Suffix Array）

定义：
后缀数组是一种数据结构，用于存储一个字符串的所有后缀的排序列表。

原理：
后缀数组的构建通常涉及对字符串的所有后缀进行排序，然后根据字典序排列。它在字符串比较、模式匹配和相似性搜索中非常有用。

Java实现示例：

import java.util.Arrays;

public class SuffixArray {
    public static int[] buildSuffixArray(String s) {
        int n = s.length();
        int[] suffixes = new int[n];
        for (int i = 0; i < n; i++) {
            suffixes[i] = i;
        }
        Arrays.sort(suffixes, (a, b) -> {
            int res = s.charAt(a) - s.charAt(b);
            if (res == 0) {
                return s.substring(a).compareTo(s.substring(b));
            }
            return res;
        });
        return suffixes;
    }

    public static void main(String[] args) {
        String s = "banana";
        int[] suffixArray = buildSuffixArray(s);
        for (int index : suffixArray) {
            System.out.println(s.substring(index));
        }
    }
}

这些算法在处理字符串搜索和比较问题时非常有用，它们各自有不同的应用场景和优势。KMP和Rabin-Karp适用于单模式匹配，Z算法和后缀数组适用于多模式匹配和更复杂的字符串分析任务。