类似phonelist 一次ac
判断失败主要有两个要点
1. 是否包含了某段的结尾结点 说明某段被此段包含
2.此段的结尾结点是否为某段的痕迹 说明此段被包含
#include<bits/stdc++.h>
using namespace std;
int trie[][];
int sum[];
int pos=; bool insert1( char *word )
{
int root=;
for(int i=;i<strlen(word);i++)
{ int ch=word[i]-'';
if(trie[root][ ch ]==)
trie[root][ ch ]=++pos;
if(sum[root]==&&root!=)return false;
sum[root]=;
root=trie[root][ch]; }
if(sum[root]!=) sum[root]=;
else return false;
return true;
} int main()
{
char word[];int cas=;
while(gets(word))
{ int ok=; memset(sum,,sizeof(sum));
memset(trie,,sizeof(trie)); if(!insert1(word)){ok=;}
while(gets(word)&&word[]!='')
{ if(ok==)continue;
if(!insert1(word)){ok=;} } if(ok)printf("Set %d is immediately decodable\n",++cas);
else printf("Set %d is not immediately decodable\n",++cas); }
}