字符串bf匹配算法java实现


/**
 * bf字符串寻找算法
 * 算法思想,使用子串对主串进行挨个匹配,如果匹配不正确,则主串向后加1,继续匹配
 * 将待匹配的主串和子串做成字符数组,方便匹配使用
 */
public class BfSearch {
    /**
     * 使用bf算法,在主串t中取匹配子串p
     * @param t 主串
     * @param p 子串
     * @return
     */
    public int bf(String t,String p){
        /**
         * 违法的寻找,直接返回-1
         * 判定方式:主串长度为0,主串为空,子串长度为0,子串为空或者子串长度大于主串长度,都为非法的查找,
         * 直接返回
         */
        if (t.length() == 0 || t == null || p.length() ==0 || p == null || t.length() < p.length()){
            return -1;
        }
        // 将字符串转成字符数组
        char[] t_array = t.toCharArray();// 主串字符数组
        char[] p_array = p.toCharArray();// 子串字符数组

        // 匹配过程
        return match(t_array,p_array);
    }

    /**
     * 字符串匹配过程
     * @param t
     * @param p
     * @return
     */
    private int match(char[] t,char[] p){
        int i = 0; // 设置主串检索下标位置
        int j = 0; // 设置子串检索下标位置
        int position = 0; // 保留检索后的开始位置
        while (i<t.length && j< p.length){
            if (t[i] == p[j]){
                // 主串位置与子串匹配成功,主串与子串下标均+1;
                i++;
                j++;
            } else {
                // 匹配失败
                i = i - j +1; // 主串索引为当前索引减去子串的索引再+1,是为了实现主串索引在不匹配情况下,向后移动一位的目的
                j = 0; // 子串检索,从0开始
            }
        }
        // 返回匹配到的索引位置
        if (i <= t.length){
            position = i - p.length;
        } else {
            position = -1;
        }
        return position;
    }

    /**
     * 测试方法
     * @param args
     */
    public static void main(String[] args) {
        BfSearch bf = new BfSearch();
        int bf1 = bf.bf("abcd", "cd");
        System.out.println(bf1);
    }
}
上一篇:flink-streaming消费kafka动态分区写入HDFS(SequenceFile)文件


下一篇:3.Mybatis中增删改查的@Param()和 Map用法