小米2018校招在线考试-编程题二

发表于 | 分类于 ，

题目 路径匹配

描述

每个路径都形如"/a/b...",
不会以 "/" 结尾
路径 "/a/b" 为路径 "/a/b/c" 的前缀路径,而并非 "/a/bc" 的前缀路径
给出已知路径及编号,求某个路径的最大前缀路径的编号
若不存在,输出 0

输入

从第 1 行开始,直到某一行出现 "-" 为止,
每行有两个字符串,第一个为路径,第二个为路径编号
接下来每行一个路径

输出

每行输出对应的路径的最大前缀路径的编号

Example

Input

/a 1
/a/b 2
/a/b/c 3
/a/b/cde 4
-
/a
/a/b
/a/b/c/d
/a/b/cd
/b

Output

1
2
3
2
0

题解

字典树

  • root 结点编号为 0
  • 若匹配完成或无法继续匹配,当前结点编号即为所求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>

using namespace std;

struct node
{
    int num;
    map<string,node*> child;
};

void build(vector<string>& strs,int num,node * root)
{
    node *tmp;
    int chnum;
    for(int i=0;i<strs.size();++i)
    {
        chnum=root->child.count(strs[i]);
        if(!chnum)
        {
            tmp=new node;
            tmp->num=root->num;
            root->child[strs[i]]=tmp;
        }
        else
        {
            tmp=root->child[strs[i]];
        }
        root=tmp;
    }
    tmp->num=num;
}

int findway(vector<string>& strs,node * root)
{
    int chnum;
    for(int i=0;i<=strs.size();++i)
    {
        if(i==strs.size())
            return root->num;
        chnum=root->child.count(strs[i]);
        if(!chnum)
        {
            return root->num;
        }
        else
        {
            root=root->child[strs[i]];
        }
    }
}

int main()
{
    node *root=new node;
    string line,tmp;
    int num;
    root->num=0;
    vector<string> strs;
    while(cin>>line&&line[0]!='-')
    {
        cin>>num;
        strs.clear();
        for(int i=1;i<=line.length();++i)
        {
            if(i==line.length()||line[i]=='/')
            {
                strs.push_back(tmp);
                tmp.clear();
            }
            else
            {
                tmp.push_back(line[i]);
            }
        }
        build(strs,num,root);
    }
    while(cin>>line)
    {
        strs.clear();
        for(int i=1;i<=line.length();++i)
        {
            if(i==line.length()||line[i]=='/')
            {
                strs.push_back(tmp);
                tmp.clear();
            }
            else
            {
                tmp.push_back(line[i]);
            }
        }
        cout<<findway(strs,root)<<endl;
    }
}