「一本通 2.3 练习 1」Immediate Decodability

题目描述

给出一些数字串，判断是否有一个数字串是另一个串的前缀。

输入输出格式

输入格式：

输入数据为多组数据，每组数据读到 9 时结束。

输出格式：

对于每组数据，如果不存在一个数字串是另一个串的前缀，输出一行 Set t is immediately decodable ，否则输出一行 Set t is not immediately decodable ，其中 t 是这一组数据的组号。

输入输出样例

输入样例#1：

01
10
0010
0000
9
01
10
010
0000
9

输出样例#1：

Set 1 is immediately decodable
Set 2 is not immediately decodable

解法

#include <bits/stdc++.h>
using namespace std;
const int N=2000000;
int son[N][10],en[N],idx,t,k,p,c,f;
string s;
int main() {
	while(cin >>s) {
		k=0; idx=0; t++;
		memset(son,0,sizeof(son));
		memset(en,0,sizeof(en));
		do {
			p=0; c=0; f=0;
			for(int i=0; s[i]; i++) {
				int u=s[i]-'0';
				if(son[p][u])
					c++;
				if(son[p][u]==0) {
					son[p][u]=++idx;
				}
				p=son[p][u];
				if(en[p]==-1)
					f=1;
			}
			if(c==s.size())
				f=1;
			en[p]=-1;
			k+=f;
		}while(cin >>s && s!="9");
		if (k>0)
			printf("Set %d is not immediately decodable\n",t);
		else
			printf("Set %d is immediately decodable\n",t);
	}
	return 0;
}