卧薪尝胆,厚积薄发。
The Book List
Date: Fri Sep 21 15:16:30 CST 2018 In Category: NoCategory

Description:

给出每本书的路径,实现一个目录。

Solution:

$trie$ 模拟即可。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
#define MAXN 200
char c[MAXN];
string getstr(char c[],int &ptr)
{
string s;
while(c[ptr] != '/' && c[ptr] != '\0')
{
s.push_back(c[ptr]);
++ptr;
}
return s;
}
struct trie
{
struct node
{
map<string,node*> tr;
bool tag;
}t[MAXN * 30];
node *root,*ptr;
node* newnode(){return ++ptr;}
void insert(char c[])
{
int ptr = 1;
node* cur = root;
while(c[ptr] != '\0' && c[ptr] != 0)
{
string s = getstr(c,ptr);++ptr;
if(cur -> tr[s] == NULL)cur -> tr[s] = newnode();
cur = cur -> tr[s];
}
cur -> tag = true;
return;
}
void print(node* k,int depth)
{
for(map<string,node*>::iterator i = k -> tr.begin();i != k -> tr.end();++i)
{
if(i -> second -> tr.size() == 0)continue;
for(int p = 1;p <= 4 * depth;++p)putchar(' ');
cout << (i -> first) << endl;
print(i -> second,depth + 1);
}
for(map<string,node*>::iterator i = k -> tr.begin();i != k -> tr.end();++i)
{
if(i -> second -> tag)
{
for(int p = 1;p <= 4 * depth;++p)putchar(' ');
cout << (i -> first) << endl;
}
}
return;
}
void reset(node* k)
{
if(k == NULL)return;
for(map<string,node*>::iterator i = k -> tr.begin();i != k -> tr.end();++i)
{
reset(i -> second);
}
k -> tr.clear();k -> tag = false;
return;
}
void init()
{
reset(root);
ptr = t;
root = ++ptr;
return;
}
}t;
int main()
{
t.init();
int cnt = 0;
while(gets(c + 1) != NULL)
{
if(c[1] == '0' && c[2] == '\0')
{
printf("Case %d:\n",++cnt);
t.print(t.root,0);
t.reset(t.root);
t.init();
}
else
{
t.insert(c);
memset(c,0,sizeof(c));
}
}
return 0;
}
In tag: 字符串-trie
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡