实验九(1).docx

数据与算法课程实验实验九最短完备子串问题引言互联网搜索已经成为了大家工作和生活的一部分。在输入一些关键词之后，搜索引擎会返回许多结果，每个结果都包含一段概括网页内容的摘要。那么这些最短摘要是怎么生成的呢？最短摘要要求包含所有的关键词。为了简化问题，我们用数字代替字符。实验内容从一个很长的整数串中查找符合以下四个要求的最短子串：子串长度最短子串包含给定整数集中的所有整数（顺序无关，全部包含即可）子串中不能重复出现给定整数集中的整数子串中允许出现给定整数集外的整数示例如下：整数集为{1234}，长串为“1233456789120003410111213100”，则长串中的子串“12334”不是符合要求的最短子串（不满足条件3），因为整数“3”存在重复；满足要求的最短子串为：“1200034”。实验中给定整数集合中的整数不存在重复。输入格式第一行：整数集长度长整数串长度。整数集长度不超过3000。第二行：整数集。整数集范围为0~10^8，每两个整数之间用空格符分开。第三行：长整数串。长整数串中元素范围为0~10^8，长整数串长度不超过10^7。每两个整数之间用空格符分开。输入示例：42212341233456789120003410111213100输出格式输出满足“实验内容”中四个要求的最短子串的长度。如上述示例，输出为“7”。实验要求用C或C++实现共有5个测试样例，难度依次递增，每个测试样例20分，满分100分。拒绝抄袭。