<题目链接>
题目大意：
给你几段只包含0,1的序列，判断这几段序列中，是否存在至少一段序列是另一段序列的前缀。
解题分析：
Trie树水题，只需要在每次插入字符串，并且在Trie树上创建节点的时候，判断路径上是否已经有完整的单词出现即可。
数组版：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char word[];
bool flag;
int trie[*][],cnt,ncase;
bool fp[*];
void Init(){
flag=true;
cnt=;
memset(fp,false,sizeof(fp));
memset(trie,,sizeof(trie));
}
void Insert(char *str){
int now=;
for(int i=;i<strlen(str);i++){
int to=str[i]-'';
if(!trie[now][to]){
trie[now][to]=++cnt;
}
now=trie[now][to];
if(fp[now])flag=false;
}
fp[now]=true;
}
int main(){
ncase=;
Init();
while(gets(word)){
if(word[]==''){
if(flag)printf("Set %d is immediately decodable\n",++ncase);
else printf("Set %d is not immediately decodable\n",++ncase);
Init();
continue;
}
Insert(word);
}
}
指针版：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; char word[];
bool flag;
struct Node{
bool fp;
Node *next[];
Node(){
fp=false;
for(int i=;i<;i++)
next[i]=NULL;
}
};
Node *root;
Node *now,*newnode;
void Insert(char *str){
now=root;
for(int i=;i<strlen(str);i++){
int to=str[i]-'';
if(now->next[to]==NULL){
now->next[to]=new Node;
}
now=now->next[to];
if(now->fp==true)flag=false; //如果路径上出现过完整的单词，则说明不符合
}
now->fp=true;
}
int main(){
flag=true;int ncase=;
root=new Node;
while(gets(word)){
if(word[]==''){
if(flag)printf("Set %d is immediately decodable\n",++ncase);
else printf("Set %d is not immediately decodable\n",++ncase);
flag=true;
root=new Node;
continue;
}
Insert(word);
}
return ;
}
2018-10-30