重学算法 系列4 - 朴素字符串匹配算法 （Brute Force算法）

朴素字符串算法通过两层循环来寻找子串，好像是一个包含模式的“模板”沿待查文本滑动。

 

public class BruteForce {

    /**
     从主串S的第pos个字符起与模式串进行比较，匹配不成功时，从主串S的第pos+1个字符重新与模式串进行比较。
     如果主串S的长度是n，模式串长度是 m，那么Brute-Force的时间复杂度是o(m*n)。
     最坏情况出现在模式串的子串频繁出现在主串S中。虽然它的时间复杂度为o(m*n)，但在一般情况下匹配时间为o(m+n)，因此在实际中它被大量使用。
     该方法的优点是：算法简单明朗，便于实现记忆。
     该方法的缺点是：进行了回溯，效率不高，而这些都是没有必要的。
     */
    public static void main(String[] args) {
        String waitForMatch = "abbacbabcbac";
        String pattern = "abc";
        int stringLength = waitForMatch.length();
        int patternLength = pattern.length();
        for (int i = 0; i < stringLength; i++) {
            // k point to the current postion
            int k = i;
            for (int j = 0; j < patternLength; j++) {
                if (waitForMatch.charAt(k) != pattern.charAt(j)) {
                    break;
                } else {
                    // OK, here is the last char
                    if (j == (patternLength - 1)) {
                        System.out.println("Find pattern at position " + i);
                        return;
                    } else {
                        // go to next char
                        k++;
                        continue;
                    }
                }
            }
        }
        System.out.println("Can't Find pattern");
    }
}