ACM非前缀编码 C++实现

ゝ一世哀愁。 2022-06-18 10:55 145阅读 0赞

非前缀编码  
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;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM非前缀编码 C++实现

非前缀编码 Description 有很多方法可以实现使用2进制序列对字符进行编码，比如典型的Huffman编码，如果在对字符的2进制编码中不存在某一个字符的编码是另

ゝ一世哀愁。/ 2022年06月18日 10:55/ 0 赞/ 146 阅读

相关 ACM零件C++实现

零件 Description 有一种工业零件，分成左右两半，它们的形状由’X’和空格表示的二维图形表示，比如：左半的零件形状如下： XXXXX XXX X

Love The Way You Lie/ 2022年06月18日 10:43/ 0 赞/ 193 阅读

相关 ACM括号编码(C++实现）

括号编码 Description S = s1 s2...s2n 是一个符合格式的括号的字符串，S能按下面两种方式编码： P编码：编码是一个整数序列P = p1

一时失言乱红尘/ 2022年06月18日 10:18/ 0 赞/ 166 阅读

相关 ACM食物链 C++实现

ACM食物链 Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动

迷南。/ 2022年05月15日 13:22/ 0 赞/ 221 阅读

相关 ACM非前缀编码 C++实现

非前缀编码 Description 有很多方法可以实现使用2进制序列对字符进行编码，比如典型的Huffman编码，如果在对字符的2进制编码中不存在某一个字符的编码是另

深碍√TFBOYSˉ_/ 2022年05月15日 13:13/ 0 赞/ 132 阅读

相关 ACM非前缀编码 C++实现

非前缀编码 Description 有很多方法可以实现使用2进制序列对字符进行编码，比如典型的Huffman编码，如果在对字符的2进制编码中不存在某一个字符的编码是另

左手的ㄟ右手/ 2022年05月15日 13:12/ 0 赞/ 133 阅读

相关 ACM零件C++实现

零件 Description 有一种工业零件，分成左右两半，它们的形状由’X’和空格表示的二维图形表示，比如：左半的零件形状如下： XXXXX XXX XX

灰太狼/ 2022年05月15日 13:09/ 0 赞/ 186 阅读

相关 ACM零件C++实现

零件 Description 有一种工业零件，分成左右两半，它们的形状由’X’和空格表示的二维图形表示，比如：左半的零件形状如下： XXXXX XXX XX

朴灿烈づ我的快乐病毒、/ 2022年05月15日 13:09/ 0 赞/ 178 阅读

相关 ACM括号编码(C++实现）

括号编码 Description S = s1 s2...s2n 是一个符合格式的括号的字符串，S能按下面两种方式编码： P编码：编码是一个整数序列P = p1

小咪咪/ 2022年05月15日 13:07/ 0 赞/ 196 阅读

相关 ACM括号编码(C++实现）

括号编码 Description S = s1 s2...s2n 是一个符合格式的括号的字符串，S能按下面两种方式编码： P编码：编码是一个整数序列P = p1

Dear 丶/ 2022年05月15日 13:07/ 0 赞/ 167 阅读