题意: 给你一堆字符串, 我们定义一个字符串可以被缩写成一个字符串 (必须是原字符串的前缀), 问你每个字符串能辨识的前缀是什么, 不能辨识意思是 (ab,abc 我们缩写成 ab);
解题思路: 可以用字典树解决, 我们把刚开始的串存进去, 然后在询问的时候, 如果当前节点的字符只被一个串走过, 那么肯定可以辨识; 如果遍历完了找不到., 那么输出他自己;
代码:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<string>
- #include<cstring>
- #define maxn 50050
- using namespace std;
- int trie[maxn][30];
- string s[2050];
- string a;
- int cnt[maxn];
- int root;
- int tot;
- void build_trie(string s)
- {
- root=0;
- int slen=s.size();
- for(int i=0;i<slen;i++)
- {
- int id=s[i]-'a';
- if(!trie[root][id])
- {
- trie[root][id]=++tot;
- }
- root=trie[root][id];
- cnt[root]++;
- }
- }
- int query(string s)
- {
- root=0;
- int slen=s.size();
- for(int i=0;i<slen;i++)
- {
- int id=s[i]-'a';
- if(cnt[root]==1)
- {
- return i-1;
- }
- root=trie[root][id];
- }
- return slen-1;
- }
- int main()
- {
- int cot=0;
- while(cin>>a)
- {
- s[++cot]=a;
- build_trie(a);
- }
- for(int i=1;i<=cot;i++)
- {
- int pos=query(s[i]);
- cout<<s[i]<<" ";
- for(int j=0;j<=pos;j++)
- cout<<s[i][j];
- cout<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2737075.html