题意翻译
本题有多组数据.每组数据给出一列以"9"结尾的仅包含'0'和'1'的字符串,如果里面有一个是另一个的子串,输出"Set &case is not immediately decodable",否则输出"Set &case is immediately decodable".换行. case从1开始计数.
感谢@Fuko_Ibuki 提供的翻译
题目描述
输入输出格式
输入格式：
输出格式：
输入输出样例
题解
算是比较简单的Trie题了吧。
首先因为懒得特殊处理，就先按长度排个序，然后从小到大枚举每个串，并且在结尾打标记。
如果经过了一个打过标记的点，说明之前有串是它的前缀。
/*
qwerta
UVA644 Immediate Decodability
Accepted
代码 C++，0.99KB
提交时间 2018-10-19 15:04:58
耗时/内存
50ms, 0KB
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s[];
bool cmp(string qaq,string qwq){
return qaq.length()<qwq.length();
}
struct emm{
int nxt[],tag;
}a[];
int main()
{
//freopen("a.in","r",stdin);
int t=;
while(++t&&cin>>s[])
{
int n=;
do{if(s[n][]=='')break;
}while(cin>>s[++n]);
n--;
sort(s+,s+n+,cmp);
int cnt=;
memset(a,,sizeof(a));
int flag=;
for(int c=;c<=n&&!flag;++c)
{
int k=;
for(int i=;i<s[c].length();++i)
{
if(!a[k].nxt[s[c][i]-''])
a[k].nxt[s[c][i]-'']=++cnt;
k=a[k].nxt[s[c][i]-''];
if(a[k].tag)flag++;
}
a[k].tag=;
}
if(!flag)
printf("Set %d is immediately decodable\n",t);
else
printf("Set %d is not immediately decodable\n",t);
}
return ;
}