Thuật toán String Matching

1. Giới thiệu

String Matching (Đối sánh chuỗi) là bài toán tìm kiếm một chuỗi mẫu (pattern) trong một chuỗi văn bản (text). Có nhiều thuật toán khác nhau với độ phức tạp và hiệu suất khác nhau.

2. Các thuật toán cơ bản

2.1. Thuật toán Brute Force

public class BruteForceStringMatch {
    public static int search(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; // Tìm thấy pattern tại vị trí i
            }
        }
        return -1; // Không tìm thấy
    }
}

2.2. Thuật toán KMP (Knuth-Morris-Pratt)

public class KMPStringMatch {
    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPSArray(pattern);

        int i = 0, j = 0;
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == m) {
                return i - j;
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
}

2.3. Thuật toán Boyer-Moore

public class BoyerMooreStringMatch {
    private static final int NO_OF_CHARS = 256;

    private static int[] buildBadCharTable(String pattern) {
        int[] badChar = new int[NO_OF_CHARS];
        Arrays.fill(badChar, -1);

        for (int i = 0; i < pattern.length(); i++) {
            badChar[pattern.charAt(i)] = i;
        }
        return badChar;
    }

    public static int search(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        int[] badChar = buildBadCharTable(pattern);

        int s = 0;
        while (s <= (n - m)) {
            int j = m - 1;
            while (j >= 0 && pattern.charAt(j) == text.charAt(s + j)) {
                j--;
            }
            if (j < 0) {
                return s;
            } else {
                s += Math.max(1, j - badChar[text.charAt(s + j)]);
            }
        }
        return -1;
    }
}

3. So sánh độ phức tạp

1. Brute Force: O(mn)
2. KMP: O(m + n)
3. Boyer-Moore: O(mn) worst case, nhưng thường tốt hơn KMP trong thực tế

4. Ứng dụng thực tế

1. Tìm kiếm văn bản
2. Phân tích DNA
3. Phát hiện virus
4. Tìm kiếm trong trình duyệt
5. Xử lý ngôn ngữ tự nhiên

5. Bài tập thực hành

1. Implement các thuật toán trên
2. So sánh hiệu suất giữa các thuật toán
3. Tìm tất cả các vị trí xuất hiện của pattern
4. Xử lý tìm kiếm với wildcard characters
5. Tối ưu thuật toán cho các trường hợp đặc biệt

6. Tài liệu tham khảo

1. String Matching Algorithms
2. KMP Algorithm
3. Boyer-Moore Algorithm