访问权限

前缀树

前缀树的属性：

前缀树的操作：

主程序 读入所有信息

构建前缀树的过程

#include<iostream>
(720)#include<vector>
#include<map>
(747)#include<unordered_map>
using namespace std;

class Trie {
public:
    bool hava_Authority = false;
    bool isInherient = true;
    unordered_map<string, Trie*> ls;
    string name;
    Trie(bool au, string str) {
        hava_Authority = au;
        name = str;
    }
    Trie() {

    }
    void insert(bool au, vector<string> str) {
        if (str.empty()) {
            this->isInherient = false;
            this->hava_Authority = true;
            return;
        }
        Trie* node = this;
        for (int i = 0; i < str.size(); i++) {
            if (node->ls.find(str[i]) == node->ls.end()) {
                Trie* tmp = new Trie(node->hava_Authority, str[i]);
                node->ls.insert(make_pair(str[i], tmp));
            }
            node = node->ls.find(str[i])->second;
        }
        if (node->isInherient)
            node->hava_Authority = au;
        node->isInherient = false;
    }

    bool query(vector<string> str) {
        Trie* node = this;
        for (int i = 0; i < str.size(); i++) {
            if (node->ls.find(str[i]) == node->ls.end()) {
                break;
            }
            node = node->ls.find(str[i])->second;
        }
        return node->hava_Authority;
    }

    void update() {
        Trie* node = this;
        for (auto it = node->ls.begin(); it != node->ls.end(); it++) {
            if (it->second->isInherient) {
                node->ls[it->first]->hava_Authority = node->hava_Authority;
            }
            node->ls[it->first]->update();
        }
    }
};

vector<string> split(string str) {
    str += "/";
    str = str.substr(1);
    vector<string> res;
    string tmp;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '/') {
            if (tmp.size())
                res.push_back(tmp);
            continue;
        }
        tmp += str[i];
    }
    return res;
}

int main() {
    Trie* root = new Trie();
    int n;
    cin >> n;
    vector<vector<string>> query;
    while (n--) {
        string t;
        cin >> t;
        query.push_back(split(t));
    }
    cin >> n;
    string a, b;
    while (n--) {
        cin >> a >> b;
        if (a == "Y") {
            root->insert(true, split(b));
        }
        else {
            root->insert(false, split(b));
        }
    }
    root->update();
    for (int i = 0; i < query.size(); i++) {
        if (root->query(query[i])) {
            cout << "Y\n";
        }
        else {
            cout << "N\n";
        }
    }
    return 0;

}

#include <bits/stdc++.h>
using namespace std;

int n, t;
string s, p;
unordered_map<string, int> mp;

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        cin >> s >> p;
        if (!mp.count(p)) mp[p] = (s == "Y");
    }
    for (int i = 0; i < n; ++i)
    {
        if (mp.count(a[i])) cout << (mp[a[i]] ? "Y" : "N") << endl;
        else
        {
            int flag = 0;
            for (int k = a[i].size() - 1; k > 0; --k)
            {
                int j = k;
                while (j > 0 && a[i][j] != '/') --j;
                string temp = a[i].substr(0, j);
                if (mp.count(temp))
                {
                    cout << (mp[temp] ? "Y" : "N") << endl, flag = 1;
                    break;
                }
                k = j;
            }
            if (!flag) cout << (mp["/"] ? "Y" : "N") << endl;
        }
    }

    return 0;
}

#include <bits/stdc++.h>
int main(){
    using namespace std;
    int k,n;
    cin >> k;
    vector<string> uncheck;//待检测的字符串
    unordered_map<string, char> index;//已知的路径和它的值
    for(int i=0;i<k;i++){
        string str1;
        cin >> str1;
        uncheck.push_back(str1);//读入待检测的字符串
    }
    cin >> n;
    for(int i =0;i<n;i++){
        string str2;
        char key;
        cin >> key;
        cin >> str2;
        if(!index.count(str2))
        index[str2] = key;//读入路径和值，如果路径相同，以第一个路径值为准
    }
    for(int i =0;i<k;i++){
        string str = uncheck[i];//待检测字符串读入str
        int j = str.size()-1;
        if(index.count(str)){
            cout << index[str] <<endl;
            continue;
        }
        while(j>0){
            if(str[j]=='/'){
                if(index.count(str.substr(0,j))){
                    cout << index[str.substr(0,j)] <<endl;
                    break;
                }
            }
            j--;
        }
        if(j==0){
            if(index.count("/"))
                cout << 'Y' <<endl;
            else
                cout << 'N' <<endl;
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5 + 10;

int idx;
unordered_map<string, int> son[N];
char tp[N];

void insert(vector<string> &ss, string mod) {
    ss.pop_back();
    int p = 0;
    for (auto &nx : ss) {
        if (!son[p].count(nx)) 
			son[p][nx] = ++idx;
        p = son[p][nx];
    }
    if (tp[p] == '*')
        tp[p] = mod[0];
}

char query(vector<string> &ss) {
	char res = 'N';
    int p = 0;
    for (auto &nx : ss) {
        if (!son[p].count(nx)) 
			break;
        p = son[p][nx];
        if (tp[p] != '*')
        	res = tp[p];
    }
    return res;
}

int main() {
	memset(tp, '*', sizeof tp);
    int n;
    cin >> n;
    vector<string> seq[n], stmp;
    stringstream ssin;
    for (int i = 0; i < n; i ++) {
		ssin.clear();
        string s;
        cin >> s;
        ssin << s;
        while (getline(ssin, s, '/')) {
            seq[i].emplace_back(s);
        }
    }
    cin >> n;
    for (int i = 1; i <= n; i ++) {
    	ssin.clear();
        string mod;
        cin >> mod;
        stmp.clear();
        string s;
        cin >> s;
        ssin << s;
        while (getline(ssin, s, '/')) {
            stmp.emplace_back(s);
        }
        stmp.emplace_back(mod);
        insert(stmp, stmp.back());
    }
    for (auto i : seq) {
        cout << query(i) << "\n";
    }
}

num_to_check = int(input().strip())
if num_to_check <= 0:
    print("N")
to_checks = []
for i in range(0, num_to_check):
    to_checks.append(input().strip())
t = int(input().strip())
paths = dict()
for i in range(0, t):
    k, v = input().strip().split(" ")
    try:
                # 测试用例竟然不是以最后一次设置的权限为准？
                # 还是意思是设置为N的权限就不准再更改了？
        flag = paths[v]
    except:          
                paths[v] = k
for p in to_checks:
        while True:
            try:
                print(paths[p])
                break
            except:
                rg = p.rfind("/")
                                # 提交的时候没注意这里，因为每次rfind都会把最右边的
                                # ‘/’去掉，所以会漏掉根目录这个情况
                if rg == 0:
                    try:
                        print(paths["/"])
                    except:
                        print("N")
                    finally:
                        break
                p = p[:rg]

#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
int main()
{
    //输入
    int N;
    cin >> N;
    vector<string> v(N, "");
    for (int i = 0; i < N; ++i)
        cin >> v[i];
    int T;
    cin >> T;
    map<string, string> preMap;
    for (int i = 0; i < T; ++i)
    {
        string s;
        string f;
        cin >> s >> f;
        preMap.insert(pair<string, string>(f, s));
    }
 
    //处理
    vector<string> ans;
    for (int i = 0; i < N; ++i)
    {
        if (preMap.find(v[i]) != preMap.end())
            ans.push_back(preMap.find(v[i])->second);
        else
        {
            string str = v[i];
            if(str.find_last_of("/\\")==0)
            {
                if(preMap.find("/")!=preMap.end())
                    ans.push_back(preMap.find("/")->second);
                else
                    ans.push_back("N");
            }
            else
            {
                while (!str.empty()&& preMap.find(str) == preMap.end())
                    str = str.substr(0, str.find_last_of("/\\"));
                if (!str.empty())
                    ans.push_back(preMap.find(str)->second);
                else
                {
                    if(preMap.find("/")!=preMap.end())
                        ans.push_back(preMap.find("/")->second);
                    else
                        ans.push_back("N");
                }
            }
        }
    }
    //输出
    for (auto& a : ans)
        cout << a << endl;
}

#include <bits/stdc++.h>
 
using namespace std;
 
struct tri_node {
    string s;
    char tag;
    unordered_map<string, tri_node*> child;
    tri_node(string tmp = "", char _tag = ' '){
        tag = _tag; 
        s = tmp;
    }
}; 
 
struct Tri {
    tri_node *root;
    Tri() {
        root = new tri_node("", 'N');
    }
 
    void insert(char *s, char ch) {
        tri_node *rt = root;
 
        char* pch = strtok(s, "/");
   
        while(pch) {
            string tmp(pch);
            if(rt->child.count(tmp) == 0) {
                rt->child[tmp] = new tri_node(tmp, rt->tag);  //孩子继承父亲的权限 
            } 
            rt = rt->child[tmp];
            pch = strtok(0, "/");
        }
         
            rt->tag = ch;
    }
 
    char getRight(char* s) {
        tri_node *rt = root;
 
        char* pch = strtok(s, "/");
        while(pch) {
            string tmp(pch);
            if(rt->child.count(tmp) == 0) {  //继承父亲节点的权限 
                return rt->tag;
            }
            rt = rt->child[tmp];
            pch = strtok(0, "/");
        }
 
        return rt->tag;
    } 
};
 
 
int main() {
    Tri tri; //路径树 
    int n;
    cin >> n;
    char s[n][256];
    for(int i = 0; i<n; ++i) cin >> s[i];
 
    int t;
    cin >> t;
    char path[256];
    char ch; 
    for(int i = 0; i<t; ++i) {
        cin >> ch >> path;
        tri.insert(path, ch);
    }
 
    for(int i = 0; i<n; ++i) {
        cout << tri.getRight(s[i]) << endl;
    }
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Node{
    string name;
    char jurisdiction = 'F';
    vector<Node*> child;
    Node* operator[](const string& key) {
        auto res = find_if(child.begin(), child.end(), [key](const auto& node) {return node->name == key; });
        if (res == child.end()) {
            child.push_back(new Node({ key }));
            return child.back();
        }
        return *res;
    }
}root;
void insert(const string& str, char lock) {
    Node* node = &root;
    string key;
    for (int i = 1; i < str.size(); i++) {
        if (str[i] == '/') {
            node = (*node)[key];
            key.clear();
        }
        else
            key += str[i];
    }
    if(!key.empty())
        node = (*node)[key];
    if (node->jurisdiction == 'F')
            node->jurisdiction = lock;
}
char search(string& str) {
    Node* node = &root;
    char inherit = root.jurisdiction;
    string key;
    for (int i = 1; i < str.size(); i++) {
        if (str[i] == '/') {
            node = (*node)[key];
            if (node->jurisdiction != 'F')
                inherit = node->jurisdiction;
            key.clear();
        }
        else
            key += str[i];
    }
    node = (*node)[key];
    if (inherit == 'F')
        inherit = 'N';
    return node->jurisdiction == 'F' ? inherit : node->jurisdiction;
}
int main() {
    int n;
    string str;
    char lock;
    cin >> n;
    vector<string> orders(n);
    for (string& order : orders)
        cin >> order;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> lock >> str;
        insert(str, lock);
    }
    for (string& order : orders)
        cout << search(order) << endl;
    return 0;
}

#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<map>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<string>v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    int t;
    cin >> t;
    map<string, char>mp;
    for (int i = 0; i < t; i++)
    {
        char c;
        string s;
        cin >> c >> s;
   if(mp[s]=='Y'||mp[s]=='N')
       continue;
        else
        mp[s] = c;
         
    }         
    
    for (int i = 0; i < n; i++)
    {
            auto iters = mp.find(v[i]);
        if (iters != mp.end())
            cout << mp[v[i]] << endl;
         
            else
            {
                auto iterr=mp.find("/");
         if(iterr!=mp.end()&&(*iterr).second=='Y')
        {
            
            cout<<'Y'<<endl;
        }
                
                
        else
         {
          auto iter = find(++v[i].begin(), v[i].end(), '/');
          if (iter == v[i].end())
              cout << "N" << endl;
          else {
           string tmp = v[i].substr(0, iter - v[i].begin());
                auto iterss = mp.find(tmp);
                if (iterss != mp.end())
                  cout << mp[tmp] << endl;
                else
                cout << "N" << endl;
                }
           } 
       }
     }
    }
一次性很难得做出来，不断的提交，不断的显示问题；
然后不断的修正去满足所有的用例，但还是想吐槽一下用例有一些真的很奇葩

这是什么鬼测试用例？？？

测试用例:

3
/mem/total
/s
/mem/totals
5
Y /mem/daemons/findme
N /mem/daemons
Y /mem/totals
Y /me
Y /

对应输出应该为:

Y
Y
Y