橡树心的J2EE

背包问题（Kanpsack Problem） | 生命游戏（Life game）

2008-02-29

字符串核对（String Match）

问题说明：

现在的一些高级程序语言对于字符串的处理支持越来越大，不过字符串搜寻本身仍是值得探讨的课题，在这里以Boyer Moore法来说明如何进行字符串说明，这个方法速度快且容易理解。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringMatch {
    private int[] skip;
    private int p;
    private String str;
    private String key;
    
    public StringMatch(String key) {
        skip = new int[256];
        this.key = key;
        
        for(int k = 0; k <= 255; k++) 
            skip[k] = key.length(); 
        for(int k = 0; k < key.length() - 1; k++) 
            skip[key.charAt(k)] = key.length() - k - 1; 
    }
    
    public void search(String str) {
        this.str = str;
        p = search(key.length()-1, str, key);
    }
    
    private int search(int p, String input, String key) {   
        while(p < input.length()) { 
            String tmp = input.substring(
                                p-key.length()+1, p+1); 

            if(tmp.equals(key))  // 比较两个字符串是否相同 
               return p-key.length()+1; 
            p += skip[input.charAt(p)]; 
        } 

        return -1; 
    }
    
    public boolean hasNext() {
        return (p != -1);
    }
    
    public String next() {
        String tmp = str.substring(p);
        p = search(p+key.length()+1, str, key);
        return tmp;
    }
    
    public static void main(String[] args) 
                                      throws IOException {
        BufferedReader bufReader = 
            new BufferedReader(
                    new InputStreamReader(System.in));
        
        System.out.print("请输入字符串：");
        String str = bufReader.readLine();
        System.out.print("请输入搜寻关键字："); 
        String key = bufReader.readLine();
        
        StringMatch strMatch = new StringMatch(key);
        strMatch.search(str);

        while(strMatch.hasNext()) { 
            System.out.println(strMatch.next()); 
        } 
    }
}