How to check whether there is a two key with the same prefix?

Question

There is map like this:

typedef std::string Path; // has this format "/<a>/<b>/<c>"

typedef std::vector<std::string>               Paths;
typedef std::map<std::string, Paths>           PathMapping;

PathMapping mathMapping; // ( "/a/b/c" --> "/a/b/c1", "a/b/c2" )

                            ( "/a/b/d" --> "/a/b/d1", "a/b/d2" )

                            ("/a/b/c/d" --> "a/b/c/d1", "a/b/c/d2" ) // not allowed

How can I check whether there are keys in the map which are substring of another key?

Wait, is it substring or prefix substring ? Or is it that one is a full prefix of the other ? — Matthieu M., Apr 20 '14 at 12:14
[Matthieu M](http://stackoverflow.com/users/147192/matthieu-m) If one is a fully prefix of another — Vardan Hovhannisyan, Apr 20 '14 at 12:20
Could you please unaccept mine and accept Matthieu M.'s one? It's the most efficient one by a long shot. — Shoe, Apr 20 '14 at 12:37

score 2 · Accepted Answer · answered Apr 20 '14 at 12:28

The keys in a map are lexicographically sorted, so that if one key A is going to be a prefix of another key B then:

A comes before B
A is also a prefix of any key between A and B

Therefore, we can perform a simple scan in the map (m here):

auto current = m.begin();
for (auto it = next(current), end = m.end(); it != end; ++it ) {
    // Note: if current is not a prefix of "it", then it cannot be a prefix
    // of any key that comes after "it", however of course "it" could
    // be such a prefix.

    // current is not a prefix of "it" if "it" is shorter
    if (it->first.size() <= current->first.size()) { current = it; continue; }

    // current is not a prefix of "it"
    if (it->first.substr(0, current->first.size()) != current->first) {
        current = it; continue;
    }

    // current is a prefix
    std::cout << "'" << current->first << "' is a prefix of '" << it->first << "'\n";
}

Note: computing a substring is not necessary, a starts_with function which does not allocate would be much better, however it does get the point across.

You can check the full code here.

score 1 · Answer 2 · edited May 23 '17 at 12:28

1

Without changing data structure:

for (const auto& p : mathMapping)
    for (const auto& s : mathMapping)
        if (starts_with(p.first, s.first))
            // collision

The C++03 version of that would be:

for (PathMapping::const_iterator p = mathMapping.begin(); p != mathMapping.end(); ++p)
    for (PathMapping::const_iterator s = mathMapping.begin(); s != mathMapping.end(); ++s)
        if (starts_with(p->first, s->first))
            // collision

where starts_with is one of the functions proposed here.

But if you can change data structure, I would split every segment by / and use a tree-like container.

edited May 23 '17 at 12:28

Community

1
1

answered Apr 20 '14 at 10:54

Shoe

74,840
36
166
272

That's rather inefficient. I get the feeling you could leverage the fact that the `map` sorts by key and therefore keys with the same prefix are clustered together. – Matthieu M. Apr 20 '14 at 12:15
@MatthieuM., yup, but I can't seem to get to a solution that is actually worth posting (see [original revision](http://stackoverflow.com/revisions/23181227/1)). By all means, please, post your own if it's better. :) – Shoe Apr 20 '14 at 12:16
I think I managed a O(N) solution (single pass). If you have the time and inclination I would appreciate a review as I may have missed something. – Matthieu M. Apr 20 '14 at 12:29

How to check whether there is a two key with the same prefix?

2 Answers2