java - 算法：字符串匹配问题

Question

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，要计算量小，速度快的算法。

Answer 1

사전나무(Trie)를 사용해 볼까요?

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

Answer 2

트리맵을 이용하여 구현 가능

으아악