字符串编码消除歧义的一个算法的问题的思路,如何使用C语言的技术实现?

Problem Description
An extensive area of research in computer science is the field of communications. With computer networks being part of everyday life of many people, the development of ways for making networks faster, more reliable and secure is constantly needed. This practical need motivates an extensive research activity in the theory behind communications.

The very first thing needed to establish any kind of communication is a common code. A code is a way of changing the form of a piece of information into some other form, in general to make it possible to convey that piece of information from one place to another. Flag codes used by boats and the Morse code used in telegraphy are examples of codes for translating letters into different forms to enable communication over different media.

More formally, a code is a set of strings composed of symbols from one alphabet. Each string defined in the code is called a code word. A message is then composed concatenating a set of code words to convey the information needed. For example, in Morse code the alphabet is composed of the symbols hyphen and dot; letter “S” is represented by the code word “...”, letter “O” is represented by the code word “---”, and therefore the distress message “SOS” in Morse code is “...---...”.

Codes for communication can have many desirable and undesirable properties such as ambiguity, entropy, redundancy, and many more. In this problem we will focus on ambiguity as a key property.

A code is ambiguous when there exists a message using that code that can be partitioned into different sequences of code words. In other words, in an ambiguous code a message may have more than one meaning. For example, consider the binary alphabet, composed of symbols {0,1}. For the code composed of the words {10, 01, 101} the message 10101 can be understood as 10-101 or 101-01 and therefore the code is ambiguous. On the other hand, for the code composed of the words {01, 10, 011} no ambiguous message exists and therefore the code is unambiguous.

As a part of the computer science community, you are required to develop a tester that checks if codes are ambiguous. In case a code is indeed ambiguous, you are also required to report the length (i.e. the number of symbols) of the shortest ambiguous message for that code.

Input
Each test case will consist on several lines. In all test cases the alphabet will be the set of hexadecimal digits (decimal digits plus the uppercase letters “A” to “F”). The first line of a test case will contain an integer N (1 <= N <= 100), the number of code words in the code. Each of the next N lines describes a code word and contains a different and non-empty string of at most 50 hexadecimal digits.
Input is terminated by N = 0.

Output
For each test case, output a single line with the length of the shortest ambiguous message forthe provided code or -1 if the code is unambiguous.

Sample Input
3
10
01
101
3
AB
BA
ABB
0

Sample Output
5
-1

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

2
vbs将字符串转换为网页实体符号
4
关于html字符串拼接的问题
5
字符串编码的一个奇怪问题
3
怎么样对一个遍历一个不规则字符串数组,找到每列中最长字符串的大小
2
Python如何判断一个字符串是否一个字典中存在的英文单词?
2
算法问题求解 关于字符串处理
4
怎么javascrpt语言实现将一个字符串转换为多个字符串构成的数组并且判断每个字符串的数组?
0
初学字符串的实际工程问题4,5,6
1
C语言字符串的排序问题如何解决?
4
一个有关如何合并字符串的问题,算法请教怎么实现的思路?
4
javascript怎么判断字符串的长度?
0
关于字符串编码和加密算法的一个问题,请问各位怎么采用C语言的实现?
0
一个有关于字符串加密编码的方式的问题,采用C语言编码字符串的实现
0
一个比较特殊的字符串计算最长相同序列的算法问题,如何使用C语言计算?
0
字符串文本加密编码算法的实现过程,采用的是C语言的方式如何实现的?
3
怎么在javascrpt里从字符串里取一个最大的数字,字符串具体如下
0
输入字符串进行一个编码的问题,采用C语言解决这个问题的技术的思路
1
特定条件的字符串的排序的一个算法问题,采用C语言的形式如何解决
0
阶梯型字符串的输出的算法问题,字符串的重复的输出简化的思路,用C语言实现
1
利用指针写一函数,实现一长字符串中两短字符串交换,从主函数输入待替换的长字符串以及替换前后两个子串?