关于字符串最佳匹配算法的问题

Question

有一个固定的字符串数组，现在需要根据一个pattern，找出该数组中匹配的元素，并按照匹配程度进行排序返回，只进行完全匹配
匹配因素：
1.pattern出现在字符串越靠前，那么该字符串的匹配程度越高
2.如果出现的位置相同，那么字符串的长度越短，排序越靠前
比如：数组["abc","ab","d"]，pattern为"ab"，那么进行匹配后，返回["ab","abc"];如果pattern为"abcd"那么返回空数组由于该算法的使用频度非常高，因此需要尽量考虑效率问题，节省开销。

Answer 1

思路：
1.对字符串数组进行排序(忽略大小写or not, "ab" < "abc" < "d"...)
2.逐个对字符串数组元素进行匹配，题目上没有说允许不允许用工具方法,比如String.contains(String str)等，如果可以使用，这题目也没什么意思；如果不允许用，就要用到数据结构与算法里边的字符串匹配算法了，叫什么来着，考研时搞过，现在忘没了~

Answer 2

找着了：数据结构算法之KMP字符串匹配算法
你认为怎么做才最好呢？时间复杂度和空间复杂度，就这俩概念了，还有代码要短小精悍，O(∩_∩)O~

Answer 3

看看性能！加载15万多个词，搜索不到1毫秒。Load dict in 1273 ms, size=157202
Search pattern: 中国
Searched in 1 ms.
Map size=389[,中国,中国上海,中国专利,中国专利局,...]Search pattern: abc
Searched in 0 ms.
Map size=0[]Search pattern: 电子
Searched in 0 ms.
Map size=130[,电子,电子世界,电子乐器,电子书,电子书下载,...]Search pattern: 中
Searched in 0 ms.
Map size=1147[,中上,中上层,中上游,中下,中下层,...]public class TreeMapTest {
private SortedMap<String,String> words = new TreeMap<String,String>();

public TreeMapTest(String[] args){
for(String s:args){
words.put(s, s);
}
}

public TreeMapTest(String dict) throws Exception{
long start = System.currentTimeMillis();
File in = new File(dict);
BufferedReader reader = new BufferedReader(new FileReader(in));
String line = reader.readLine();
while(null != line){
String[] ws = line.split("\t");
words.put(ws[0], ws[0]);
line = reader.readLine();
}
reader.close();
long end = System.currentTimeMillis();
System.out.println("Load dict with " + (end-start) + " ms, size=" + words.size());
}

public void search(String pattern){
System.out.println("Search pattern: " + pattern);
long start = System.currentTimeMillis();
String fromKey = pattern;
String toKey = null;
int length = pattern.length();
if( length == 1){
toKey = String.valueOf((char)(pattern.charAt(0)+1));
}else{
StringBuilder sb = new StringBuilder();
sb.append(pattern.substring(0, length-1));
sb.append((char)(pattern.charAt(length-1)+1));
toKey = sb.toString();
}
SortedMap<String,String> result =  words.subMap(fromKey, toKey);
long end = System.currentTimeMillis();
System.out.println("Searched in " + (end-start) + " ms.");
show(result);
}

public void show(SortedMap<String,String> map){
System.out.println("Map size=" + map.size() + "[");
Set<String> keys = map.keySet();
for(String key:keys){
System.out.print(",");
System.out.print(key);
}
System.out.println("]");
} public static void main(String[] args) throws Exception {
// String[] strs = {"abc","ab","d","abcde","da","db","dbc","ac","aca","中国","中华人民共和国","中国人","中国龙"};
// TreeMapTest test = new TreeMapTest(strs);
TreeMapTest test = new TreeMapTest("your dict file");


test.search("中国");
test.search("abc");
test.search("电子");
test.search("中");
}}

Answer 4

public class PatternDemo { static Set<String> set = new HashSet<String>(); static Map<String, Integer> map = new HashMap<String, Integer>(); public void compute(String[] args, String pattern) {
for (String a : args) {
for (int i = 0; i < a.length(); i++) { for (int j = i; j < a.length(); j++) {
String situa = a.substring(i, j + 1);
if (situa.contains(pattern)) {
set.add(a);
} }
}
}
} public String[] sort(String[] str, String pattern) {
for (int i = 0; i < str.length - 1; i++) {
for (int j = i + 1; j < str.length; j++) {
if ((str[i].length() - pattern.length())
- (str[j].length() - pattern.length()) > 0) {
String temp = str[i];
str[i] = str[j];
str[j] = temp;
} }
}
return str;
} public static void main(String[] args) {
long start = System.currentTimeMillis(); args = new String[] { "abcdes", "bc", "ab", "abc", "d" };
String pattern = "bc";
PatternDemo pd = new PatternDemo(); pd.compute(args, pattern); String[] result = new String[set.size()]; int flag = 0;
for (String a : set) {
result[flag++] = a;
}

// 排序
pd.sort(result, pattern);
for (String a : result) {
System.out.println(a);
}
long end = System.currentTimeMillis();
System.out.println("Time used: " + (end - start) + " ms, result size="
+ result.length);
}
}

Answer 5

不知道这个效率怎么样，高手来。
 public static void main( String[] args )
    {
        args = new String[]
        { "abcdes", "bc", "ab", "abc", "d" };
        Pattern p = Pattern.compile( "bc" );
        List list = new ArrayList();
        List tmplist = new ArrayList();
        for( int i = 0; i < args.length; i ++ )
        {
            Matcher m = p.matcher( args[i] );
            if( m.matches() )
            {
                list.add( args[i] );
            }
            else if( !m.matches() && m.find() )
            {
                tmplist.add( args[i] );
            }
        }
        Collections.sort( tmplist, new Comparator()
        {
            
            @Override
            public int compare( Object o1, Object o2 )
            {
                String s1 = ( String ) o1;
                String s2 = ( String ) o2;
                
                if( s1.length() >= s2.length() )
                    return 1;
                else
                    return 0;
            }
            
        } );
        
        list.addAll( tmplist );
    
    }