非前綴編碼
Description
有很多方法可以實現使用2進制序列對字符進行編碼，比如典型的Huffman編碼，如果在對字符的2進制編碼中不存在某一個字符的編碼是另一個字符編碼的前綴，那麼就稱這種編碼方式為非前綴編碼，Huffman編碼就是一種非前綴編碼。比如A：00 B：10 C：0100 D：0101 則這種編碼為非前綴編碼；A:01 B:10 C:010 D:0000，則這種編碼為前綴編碼。
請寫一個程序，判斷編碼是前綴編碼還是非前綴編碼。
輸入：
第一行是一個整數K，表示有多少個測試用例，以後每行一個測試用例。每個測試用例為若干個字符串，字符串之間有空格隔開（最大長度不超過1000）。
輸出：
每行輸出一個測試用例的結果。如果是非前綴編碼輸出Yes，否則輸出No。
Sample Input
2
01 10 0010 0000
01 10 010 0000
Sample Output
Yes
No
#include<iostream>
#include<stdlib.h>
#define N 1000
using namespace std;
char str[N][N];
int len[N];
int cmp(const void *a,const void *b)
{
return strcmp((char*)a,(char*)b);
}
bool check(int i)
{
int k=len[i],j=0;
while(j<k)
if(str[i][j++]!=str[i+1][j++])
return false;
return true;
}
int main()
{
int k;
cin>>k;
while(k--)
{
scanf("%s",str[0]);
int n=1;
int flag=false;
while(getchar()!='\n')
{
scanf("%s",str[n++]);
}
qsort(str,n,sizeof(str[0]),cmp);
len[0]=strlen(str[0]);
int i=0;
for(i=1;i<n;i++)
{
len[i]=strlen(str[i]);
if(len[i-1]>len[i])
continue;
else
{
if(check(i-1))
{
flag=true;
break;
}
}
}
if(flag)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
return 0;
}
