算法高手来看看

来源：百度知道 编辑：UC知道 时间：2024/05/31 04:10:39
给你一段数字S1(都是0 .. 9)比如"0123456789"
求另一串数字S2，使其没有在S1中出现过，且s2尽量短
如果有多组则输出大小排序最小的，这组数据的输出为“00”

那些指数级的算法我就不看了....
只说说想法就行，最好附上c++ 或 pascal 的程序
使s2没有在S1中出现过 就是pos(s2, s1)=0 ，s2不是s1子串
--------------------------------------
建了后缀树又怎么实现？能不能说明白点。

若S1长度为n
后缀树建树的时候最坏情况不是O(n^2)吗,每个字符分裂一次的话(虽然实际上不可能).
直接从小到大枚举S2,用KMP匹配复杂度是O(n^2)的.最坏情况下需要枚举的个数比n稍大,一次匹配O(n),S2长度可以无视.

建了后缀树的话只要由根开始逐层检查结点的子结点数是否为10就可以了.不为10时,输出一路上的字符,再输出最先缺少的那个字符.

没看懂题,怎么才叫没出现过?

看不懂

用后缀树

我是这么做的:
0-9可以看成是(11 1111 1111)
对应的数字就对应位置上的1.
初始的数字为0,然后S1中的数字变成对应二进制,然后与初始数字相或.
当S1检验完毕后,相应位置为0的对应十进制数字就是S2的解.