欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java实现sunday算法示例分享

程序员文章站 2024-02-21 20:32:34
字符串匹配查找算法中,最著名的两个是kmp算法(knuth-morris-pratt)和bm算法(boyer-moore)。两个算法在最坏情况下均具有线性的查找时间。但是在...

字符串匹配查找算法中,最著名的两个是kmp算法(knuth-morris-pratt)和bm算法(boyer-moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上,kmp算法并不比最简单的c库函数strstr()快多少,而bm算法则往往比kmp算法快上3-5倍(未亲身实践)。但是bm算法还不是最快的算法,这里介绍一种比bm算法更快一些的查找算法sunday算法。

sunday算法的思想和bm算法中的坏字符思想非常类似。差别只是在于sunday算法在匹配失败之后,是取目标串中当前和pattern字符串对应的部分后面一个位置的字符来做坏字符匹配。当发现匹配失败的时候就判断母串中当前偏移量+pattern字符串长度+1处(假设为k位置)的字符在pattern字符串中是否存在。如果存在,则将该位置和pattern字符串中的该字符对齐,再从头开始匹配;如果不存在,就将pattern字符串向后移动,和母串k+1处的字符对齐,再进行匹配。重复上面的操作直到找到,或母串被找完结束。动手写了个小例子来实现以下这个算法。

在代码中,实现了两种字符串匹配算法,一种是sunday方式,一种是普通的每次移动一位的方式,二者的效率对比在main函数中有,都是纳秒级别。算法的详细步骤,在代码中已经添加了相应的注释。关于bm算法,下次空了再一起对照着分析。

复制代码 代码如下:

import java.util.hashmap;
import java.util.linkedlist;
import java.util.list;
import java.util.map;

/**
 * @author scott
 * @date 2013年12月28日
 * @description
 */
public class sundysearch {
    string text = null;
    string pattern = null;
    int currentpos = 0;

    /**
     * 匹配后的子串第一个字符位置列表
     */
    list<integer> matchedposlist = new linkedlist<integer>();

    /**
     * 匹配字符的map,记录改匹配字符串有哪些char并且每个char最后出现的位移
     */
    map<character, integer> map = new hashmap<character, integer>();

    public sundysearch(string text, string pattern) {
        this.text = text;
        this.pattern = pattern;
        this.initmap();
    };

    /**
     * sunday匹配时,用来存储pattern中每个字符最后一次出现的位置,从左到右的顺序
     */
    private void initmap() {
        for (int i = 0; i < pattern.length(); i++) {
            this.map.put(pattern.charat(i), i);

        }
    }

    /**
     * 普通的字符串递归匹配,匹配失败就前进一位
     */
    public list<integer> normalmatch() {
        //匹配失败,继续往下走
        if (!matchfromspecialpos(currentpos)) {
            currentpos += 1;

            if ((text.length() - currentpos) < pattern.length()) {
                return matchedposlist;
            }
            normalmatch();
        } else {
            //匹配成功,记录位置
            matchedposlist.add(currentpos);
            currentpos += 1;
            normalmatch();
        }

        return matchedposlist;
    }

    /**
     * sunday匹配,假定text中的k字符的位置为:当前偏移量+pattern字符串长度+1
     */
    public list<integer> sundaymatch() {
        // 如果没有匹配成功
        if (!matchfromspecialpos(currentpos)) {
            // 如果text中k字符没有在pattern字符串中出现,则跳过整个pattern字符串长度
            if ((currentpos + pattern.length() + 1) < text.length()
                    && !map.containskey(text.charat(currentpos + pattern.length() + 1))) {
                currentpos += pattern.length();
            }else {
                // 如果text中k字符在pattern字符串中出现,则将text中k字符的位置和pattern字符串中的最后一次出现k字符的位置对齐
                if ((currentpos + pattern.length() + 1) > text.length()) {
                    currentpos += 1;
                } else {
                    currentpos += pattern.length() - (integer) map.get(text.charat(currentpos + pattern.length()));
                }
            }

            // 匹配完成,返回全部匹配成功的初始位移
            if ((text.length() - currentpos) < pattern.length()) {
                return matchedposlist;
            }

            sundaymatch();
        }else {
            // 匹配成功前进一位然后再次匹配
            matchedposlist.add(currentpos);
            currentpos += 1;
            sundaymatch();
        }
        return matchedposlist;
    }

    /**
     * 检查从text的指定偏移量开始的子串是否和pattern匹配
     */
    public boolean matchfromspecialpos(int pos) {
        if ((text.length()-pos) < pattern.length()) {
            return false;
        }

        for (int i = 0; i < pattern.length(); i++) {
            if (text.charat(pos + i) == pattern.charat(i)) {
                if (i == (pattern.length()-1)) {
                    return true;
                }
                continue;
            } else {
                break;
            }
        }

        return false;
    }

    public static void main(string[] args) {
        sundysearch sundysearch = new sundysearch("hello 啊啊 阿道夫 adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");

        long begin = system.nanotime();
        system.out.println("normalmatch:" + sundysearch.normalmatch());
        system.out.println("normalmatch:" + (system.nanotime() - begin));

        begin = system.nanotime();
        system.out.println("sundaymatch:" + sundysearch.sundaymatch());
        system.out.println("sundaymatch:" + (system.nanotime() - begin));

    }
}