字符串匹配——BF

概念

单模式字符串匹配就是一个字符串a和另一个字符串b进行匹配，一般而言，a的长度远大于b，我们在a中查找是否包含b。我们将字符串a称为主串，字符串b称为模式串。

BF算法

BF算法成为暴力匹配算法，又叫做朴素匹配算法。也是最简单的，我们经常用到的算法。最简单的方法就是每次比对m个字符，最坏情况下比较n-m+1次，BF算法的最坏情况时间复杂度为O(n*m)。

步骤
1 模式串一个个与主串字符比较，如果相同接着比较，不相同则主串移动一位，接着和模式串从头开始一个个比较

package com.github.strings;
public class bf {
    public static int search(String str,String pat){
        int sLen = str.length();// 主字符串
        int pLen = pat.length();// 模式串长度
        // 需要匹配的次数
        for (int i=0;i<=sLen-pLen;i++){
            int j ;
            // 遍历模式串
            for (j=0;j<pLen;j++){
                if (pat.charAt(j)!=str.charAt(i+j)){
                    break;
                }
            }
            // 如果j移动到模板末尾了 说明匹配成功了
            if (j==pLen) return i ;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(search("helloWorld","hello"));
        System.out.println(search("helloWorld","World"));
        System.out.println(search("aaaaaaab","aaab"));
        System.out.println(search("helloWorld","lo"));
        System.out.println(search("aacaaab","aaab"));
    }
}