我需要一个稍微不同的多图

Question

我正在寻找一个C++容器类,这很像多图,但略有不同.容器将存储成对的字符串.但是当我使用键K从容器中检索项目时,我想找到K以项目自己的键开头的所有项目.

EG如果我使用键"abcde",我想找到带有"adc"和"abcde"键的项目,而不是"abcqz".

或者以伪C++形式:

multimap2<string, string>  myMultiMap;
myMultiMap.insert( pair("abcde", "hello"));
myMultiMap.insert( pair("abc",   "Hi"));
myMultiMap.insert( pair("abcqz", "goodbye"));

// prints 2
cout << myMultiMap.count("abcde") << endl;

// prints "hello"  and  "Hi"
cout << myMultiMap.everything_which_matches("abcde") << endl;

// prints "Hi"
cout << myMultiMap.everything_which_matches("abc") << endl;

// prints "goodbye"
cout << myMultiMap.everything_which_matches("abcqz") << endl;

插入时间并不重要,但我需要快速访问这些项目.是否可以通过创建一个特殊的<运算符来使用普通的Multimap执行此操作？我的预感是我需要普通的<操作符进行插入,还需要一个特殊的操作符进行检索.

谢谢

雨果

Answer 1

我建议使用trie.

基本上你有一棵树,每个唯一字符有1个节点.对于查找和插入,您的算法将为O(m),其中m是字符串的长度.

所以按照你的例子:

"abcde", "hello" 
 "abc",  "Hi"
"abcqz", "goodbye"

然后你会有以下trie:

       a
       |
       b
       |
       c       (c holds data of hi)
     /  \
    d    q
    |    |
    e    z (z holds data of goodbye)    (e holds data of hello)

要进行查找,只需从根节点(上面未显示的根节点)开始,然后按照输入字符串中的下一个字符进行操作.每次到达具有数据结果的节点时,都会将其作为输出字符串之一包含在内.

所以搜索abcde会给你:"嗨","你好",如你所愿.它不会给你"再见",因为你没有遍历那个结果节点.