字符串包含关键字的最佳算法

Question

String key[] = {key1,ke2,key3,.........,keyn};
String org = "XXXXXXXXXXXXXXX.........................XXXXXXXXXXXXXXXX";
or
StringBuffer org = new StringBuffer(""XXXXXXXXXXXXXXX.........................XXXXXXXXXXXXXXXX"");
说明:key[] 数组中的元素有很多,可以将其放入其他的数据结构中.
     org是一个长度不定,字符串(可能会非常长的).数据类型可根据实际的算法作更改.
    
要求:判断字符串org中是否包含有key[]中的关键字.
    
直接:
for(int i=0;i<key.lenth;i++){
boolean result = org.contains(key[i]);
...............................
}
这样的回复就别回了...在线等待.

Answer 1

你的数据类型可变,建议分别放入list中,遍历一个list,然后用contains方法比较.

Answer 2

要求出所有key[n]在org的位置没?

Answer 3

等高手出现,下面不是最快的,就当我扔个砖头/*
run:
file length:19004643byte
false
用时:62969ms对空间优化后时间变长了
成功生成（总时间：1 分钟 3 秒）public class Main {    public static void main(String[] args) throws FileNotFoundException, IOException {
        File ff = new File("d:\\1.txt");
        System.out.println("file length:"+ff.length()+"byte");
        String[] keys = {"123", "124", "asd"};
        long t=System.currentTimeMillis();
        System.out.println("" + Main.contains(keys, new java.io.FileInputStream(ff)));
        System.out.println("用时:"+(System.currentTimeMillis()-t)+"ms");
    }
    //长度不确定用流
    public static boolean contains(final String[] keys, java.io.InputStream is) throws IOException {
        java.util.HashMap<Integer,Vector<Integer>> head = new java.util.HashMap<Integer,Vector<Integer>> ();
        final byte[][] kmap = new byte[keys.length][];////////这里要优化
        for (int i = keys.length - 1; i > -1; i--) {
            kmap[i] = keys[i].getBytes();
            if (keys[i] != null){
                if(!head.containsKey(keys[i].charAt(0))){
                    Vector<Integer>lis=new Vector();
                    lis.add(i);
                    head.put((int)keys[i].charAt(0), lis);
                }else{
                    head.get((int)keys[i].charAt(0)).add(i);
                }
            }
        }
        final Vector l = new Vector();
        class filer {
             boolean[] ishead;
            int post = 0;
            Integer []indexs;
            int len;
            filer(Vector<Integer> g) {
                len = g.size();
                ishead = new boolean[len];
                indexs=new Integer[len];
                int i=0;
                for(Object o:g.toArray()){
                    indexs[i++]=(Integer) o;
                }
            }            boolean put(int i) {
                for (int j = 0; j< len; j++) {
                    if (!ishead[j]) {
                        if(kmap[indexs[j]][post]!=i){
                            ishead[j] = true;
                        }
                    }
                }
                int flag = 0;
                post++;
                for (int j = ishead.length - 1; j > -1; j--) {//检查是否找出key
                    if (!ishead[j]) {
                        if (post == kmap[indexs[j]].length) {
                            return true;
                        }
                        flag++;
                    }
                }
                if (flag == 0) {//全失败
                    l.remove(this);
                }
                return false;
            }
        }
        int d, post = 0;
        do {
            d = is.read();
            if (head.containsKey(d)) {
                l.add(new filer(head.get(d)));
            }
            for (int i = l.size() - 1; i > -1; i--) {
                if (((filer) l.get(i)).put(d)) {
                    return true;
                }
            }
            post++;
        } while (d != -1);
        is.skip(0);
        return false;
    }
}
*/

Answer 4

没要求..找一个.BREAK出来就OK了..按道理来讲..找一个和多个的优化策略应该是一样的..

Answer 5

新索引文件：
A{1}
B{2,7}
C{3}
D{4,8,9} 思路反了吧，这样你还得先分析字符串，建立索引文件。去搜索下字符串匹配算法吧，这应该有现成的算法，不过都比较复杂，这样理论性高的算法。我看不懂。呵呵