算法：字符串匹配问题

import java.util.HashMap;
import java.util.Map;

public class TestMap {

    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("1", "1");
        map.put("21", "1");
        map.put("22", "1");
        map.put("23", "1");
        map.put("24", "1");
        map.put("25", "1");
        map.put("26", "1");
        map.put("27", "1");
        map.put("28", "1");
        map.put("29", "1");
        map.put("311", "1");
        map.put("312", "1");
        map.put("313", "1");
        map.put("314", "1");
        map.put("315", "1");
        map.put("316", "1");
        map.put("317", "1");
        map.put("318", "1");
        map.put("319", "1");
        map.put("321", "1");
        map.put("322", "1");
        map.put("323", "1");
        map.put("324", "1");
        map.put("325", "1");
        map.put("326", "1");
        map.put("327", "1");
        map.put("328", "1");
        map.put("329", "1");
        map.put("331", "1");
        map.put("332", "1");
        map.put("333", "1");
        map.put("334", "1");
        map.put("335", "1");
        map.put("336", "1");
        map.put("337", "1");
        map.put("338", "1");
        map.put("339", "1");

        String str = "3333333333";
        for (int i=0; i<str.length(); i++) {
            String res = map.get(str.substring(0, i));
            System.out.println(res);
        }
    }
}

有如上测试类，map中的key的规则是长的key从首字符开始不包含完整的短的key，然后给定一个字符串，从第一个字符匹配到最优的map的值，有没有更好的算法？

算法描述：现有上百万条长短不一的key，key的规则是长的key从首字符开始不包含完整的短的key，比如说key(21)不包含key(1),key(321)不包含key(3,32)等，然后给定一个字符串从首字符开始最优匹配，比如说有字符串222，最后在给定的key（21,22，23）中匹配22，要计算量小，速度快的算法。

---

可以用treemap实现

NavigableMap<String, String> map = new TreeMap<>();
        map.put("11","1");
        map.put("21","1");
        map.put("22","1");
        map.put("23","1");
        map.put("24","1");
        map.put("25","1");
        map.put("26","1");
        map.put("27","1");
        map.put("28","1");
        map.put("29","1");

        String lowerKey = map.lowerKey("114");
        System.out.println(StringUtils.startsWith("114", lowerKey) ? lowerKey : null);

---

试试看字典树（Trie）？

https://en.wikipedia.org/wiki...