【Week 15 作业B】ZJM与生日礼物

题目描述

ZJM 收到了 Q老师 送来的生日礼物，但是被 Q老师 加密了。只有 ZJM 能够回答对 Q老师 的问题，Q老师 才会把密码告诉 ZJM。
Q老师 给了 ZJM 一些仅有 01 组成的二进制编码串, 他问 ZJM：是否存在一个串是另一个串的前缀.

输入格式

多组数据。每组数据中包含多个仅有01组成的字符串，以一个9作为该组数据结束的标志。

输出格式

对于第 k 组数据(从1开始标号)，如果不存在一个字符串使另一个的前缀，输出"Set k is immediately decodable"，否则输出"Set k is not immediately decodable"。

每组数据的输出单独一行

输入样例

01
10
0010
0000
9
01
10
010
0000
9

样例输出

Set 1 is immediately decodable
Set 2 is not immediately decodable

思路

每输入一个字符串，便插入到一颗字典树中，同时判断该字符串是否是已插入字符串的子串或者存在其他已插入字符串是该字符串的子串。详见insert函数。
若上述条件成立，则已经可得出结论，该组其他字符串可不用再一一插入字典树

代码

#include <iostream>
#include <string.h>
using namespace std;
bool jud;
struct Trie{
	static const int N=10000,charset=5;
	int tot,root,child[N][charset],flag[N];
	Trie(){
		memset(child,-1,sizeof(child));
		root=tot=0;
	}
	void clear(){
		memset(child,-1,sizeof(child));
		root=tot=0;
	}
	void insert(char*str){
		int now=root,len=strlen(str);
		for(int i=0;i<len;i++)
		{
			int x=str[i]-'0';
			if(child[now][x]==-1)
			{
				child[now][x]=++tot;
				flag[now]=0;
			}
			else if(i==len-1||flag[child[now][x]]==1)jud=true;
			now=child[now][x];
		}
		flag[now]=1;
	}
};
Trie tt;
int main(int argc, char** argv) {
	int n=1;
	jud=false;
	char str[100];
	while(scanf("%s",str)!=EOF)
	{
		if(str[0]-'0'!=9)
		{
			if(!jud)
				tt.insert(str);	
		}
		else
		{
			if(jud)
				printf("Set %d is not immediately decodable\n",n);
			else
				printf("Set %d is immediately decodable\n",n);
			jud=false;
			tt.clear();
			n++;
		}
	}
	return 0;
}