Java实现Sunday字符串匹配算法

简介

在字符串处理中，字符串匹配是一个常见的需求，即确定一个较短的字符串（模式串）是否存在于一个较长的字符串（主串）中，并找到其出现的位置。Sunday字符串匹配算法是一种高效的字符串匹配算法，由Daniel M. Sunday在1990年提出。它通过对模式串和主串的字符分析，减少不必要的字符比较，从而提高匹配效率。

基础概念

核心思想

Sunday算法的核心思想是在匹配过程中，当发现不匹配的字符时，不是简单地将模式串向右移动一位，而是根据主串中当前匹配位置的下一个字符来决定模式串的移动距离。如果该字符在模式串中不存在，那么可以将模式串直接移动到该字符之后，从而跳过大量不必要的比较。

移动规则

假设主串为 text，模式串为 pattern。在匹配过程中，若在主串的第 i 个位置发现不匹配，此时查看主串中第 i + pattern.length() 位置的字符 c。

如果 c 不在模式串中，那么将模式串直接移动到 i + pattern.length() + 1 的位置。
如果 c 在模式串中，设其在模式串中的最右位置为 j，则将模式串移动到 i + pattern.length() - j 的位置。

使用方法

初始化

在使用Sunday算法之前，需要定义主串和模式串。在Java中，可以使用 String 类型来表示：

String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";

实现匹配函数

实现一个函数来执行Sunday字符串匹配算法。该函数接收主串和模式串作为参数，并返回模式串在主串中首次出现的位置，如果未找到则返回 -1。

常见实践

简单匹配示例

public class SundayAlgorithm {
    public static int sundaySearch(String text, String pattern) {
        int textLen = text.length();
        int patternLen = pattern.length();
        int i = 0;

        while (i <= textLen - patternLen) {
            int j = 0;
            while (j < patternLen && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == patternLen) {
                return i;
            }
            if (i + patternLen >= textLen) {
                break;
            }
            char nextChar = text.charAt(i + patternLen);
            int lastIndex = pattern.lastIndexOf(nextChar);
            if (lastIndex == -1) {
                i += patternLen + 1;
            } else {
                i += patternLen - lastIndex;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = sundaySearch(text, pattern);
        if (result!= -1) {
            System.out.println("模式串在主串中的位置是: " + result);
        } else {
            System.out.println("未找到模式串");
        }
    }
}

处理大文本

在处理大文本时，可以考虑分块读取文本，避免一次性将整个大文本加载到内存中。例如，可以使用 BufferedReader 逐行读取文本，并在每一行上执行Sunday匹配算法。

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class SundayLargeTextSearch {
    public static int sundaySearch(String text, String pattern) {
        // 与上述实现相同
    }

    public static void main(String[] args) {
        String pattern = "examplePattern";
        String filePath = "largeTextFile.txt";

        try (BufferedReader br = new BufferedReader(new FileReader(filePath))) {
            String line;
            int lineNumber = 1;
            while ((line = br.readLine())!= null) {
                int result = sundaySearch(line, pattern);
                if (result!= -1) {
                    System.out.println("在第 " + lineNumber + " 行找到模式串，位置是: " + result);
                }
                lineNumber++;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

最佳实践

预处理模式串

可以在匹配之前对模式串进行预处理，构建一个字符位置表，这样在匹配过程中查找字符位置时可以更高效。例如，可以使用一个数组来记录每个字符在模式串中的最右位置。

public class SundayOptimized {
    public static int[] buildCharTable(String pattern) {
        int[] table = new int[256];
        for (int i = 0; i < 256; i++) {
            table[i] = -1;
        }
        for (int i = 0; i < pattern.length(); i++) {
            table[pattern.charAt(i)] = i;
        }
        return table;
    }

    public static int sundaySearch(String text, String pattern) {
        int textLen = text.length();
        int patternLen = pattern.length();
        int[] charTable = buildCharTable(pattern);
        int i = 0;

        while (i <= textLen - patternLen) {
            int j = 0;
            while (j < patternLen && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == patternLen) {
                return i;
            }
            if (i + patternLen >= textLen) {
                break;
            }
            char nextChar = text.charAt(i + patternLen);
            i += patternLen - (charTable[nextChar] == -1? -1 : charTable[nextChar]);
        }
        return -1;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = sundaySearch(text, pattern);
        if (result!= -1) {
            System.out.println("模式串在主串中的位置是: " + result);
        } else {
            System.out.println("未找到模式串");
        }
    }
}

多线程匹配

对于非常大的文本，可以考虑使用多线程进行匹配，将文本分成多个部分，每个线程负责一部分文本的匹配，最后汇总结果。

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class SundayMultiThreadSearch {
    public static int sundaySearch(String text, String pattern) {
        // 与上述实现相同
    }

    public static class TextSearchTask implements Callable<Integer> {
        private final String text;
        private final String pattern;

        public TextSearchTask(String text, String pattern) {
            this.text = text;
            this.pattern = pattern;
        }

        @Override
        public Integer call() throws Exception {
            return sundaySearch(text, pattern);
        }
    }

    public static void main(String[] args) {
        String pattern = "examplePattern";
        String largeText = "a very large text...";
        int numThreads = 4;
        int partSize = largeText.length() / numThreads;

        ExecutorService executorService = Executors.newFixedThreadPool(numThreads);
        Future<Integer>[] futures = new Future[numThreads];

        for (int i = 0; i < numThreads; i++) {
            int start = i * partSize;
            int end = (i == numThreads - 1)? largeText.length() : (i + 1) * partSize;
            String partText = largeText.substring(start, end);
            futures[i] = executorService.submit(new TextSearchTask(partText, pattern));
        }

        for (Future<Integer> future : futures) {
            try {
                int result = future.get();
                if (result!= -1) {
                    System.out.println("找到模式串");
                    executorService.shutdown();
                    return;
                }
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
        }
        System.out.println("未找到模式串");
        executorService.shutdown();
    }
}

小结

Sunday字符串匹配算法通过巧妙的移动规则，在字符串匹配中能够显著提高匹配效率，尤其适用于较长文本的匹配。通过理解其基础概念、掌握使用方法，并应用常见实践和最佳实践，开发者可以在Java项目中高效地实现字符串匹配功能。无论是简单的文本处理还是处理大文本、多线程场景，Sunday算法都能提供有效的解决方案。