- 论坛徽章:
- 0
|
本帖最后由 NalaGinrut 于 2010-02-06 16:54 编辑
一个串压缩问题，将所有的串压缩为一个串，但每个串都可以在这个压缩串中被搜索到。不知道楼主是不是用来做搜索的？
给一个简单的算法，最坏情况空间复杂度为：串最大长度*串数目，时间复杂度感觉也不是太大，我估摸着楼主既然是要串压缩，可能更注重空间复杂度。不能保证最优解，且每次只能得到确定的压缩串。
令a_i(i=0,1,2...)为串集合A中所有待压缩的串，b为已经压缩好的串，设立松散匹配函数func，松散匹配只保证b中存在与a_i中对应元素排列次序完全相同的元素序列，但不保证元素连续出现。伪C定义如下：
func(a,b)
{
while( b != END)
{
if(a == b)
a=a.next;//匹配到串a中一个元素，则比较下一个；
if(a == END)
return OK;//如果a先于b结束，则b中存在a的一个松散匹配，返回OK；
b=b.next;
}
return a.rest;//b先于a结束，则b中不存在a的一个完整松散匹配，这时候返回剩下的a元素；
}
算法如下：
1、从A中任取a_i，若A为空，则执行4；
2、调用func(a_i ,b)，若返回值为OK，则执行1，否则执行3；
3、将func返回的部分合并到b的末尾，执行1；
4、返回串b，为已压缩好的串。
PS：如果想得到不确定的压缩串，可以加入随机处理，可以进行随机插入。
不能保证最优解，因为松散匹配时不会进行折返，这个松散匹配算法比较简单。但是可以保证在当前a_i在b中已经匹配到的元素不会重复插入。 |
|
免费注册
发表于 2010-02-04 21:30
发表于 2010-02-05 13:51
