Chinaunix

标题: 刚碰上的问题,希望能找到最好的解决方法 [打印本页]

作者: welf 时间: 2008-01-13 15:48
标题: 刚碰上的问题,希望能找到最好的解决方法
有一个链表，节点内容可能是若干个有序字符串的其中一个字符或字符串本身，举个例子，字符串的集合是"abcd","efgh"
链表是a->b->c->d->e->g->h->abcd->efgh.现要对其处理，a->b->c->d能顺序合并成"abcd',e->g->h就不行，应此去掉这三个节点，最后得到的链表是abcd->abcd->efgh.
因为链表巨大，理想的情况是只遍历一趟，尽量不占用额外的空间。

作者: caijimin 时间: 2008-01-13 19:56
如果字符串的集合是预先已知的，应该可以。否则涉及到回溯，只遍历一遍不大可能。

作者: Nzm 时间: 2008-01-13 20:39
觉得可以分配点空间存储有可能要合并的字符或字符串.这样还是可能一次遍历的.

作者: cuichaox 时间: 2008-01-13 21:30
如果预定义子串中，有“abc”， “abcde”。是优先匹配长的，还是短的?

初步考虑, 可以实现：
两个状态集合:
   静态的(集合元素不变化)， - 包括所有要匹配的字符串。
   动态的(集合元素变化) - 记录匹配到"中途"的状态。

如果，字符串的集合是"abcd","efgh"
静态状态机集合中有两个状态：
   //状态应该使用恰当的类，或数据结构实现，下面只简单描述
      1: {dest="abcde", nMatched=0};
      2: {dest="efgh",nMatched=0};
      dest=要匹配的字符串， nMatched=已经匹配成功的字符个数

如果当前列表中得到下一个字母为'*',  对所有状态机输入这个字母'*'。for each state:
(1)如果对“静态集合”中一个状态产生了匹配(dest[nMatched]='*')，生成新状态(nMatched加了1)插到"动态集合"。
(2)如果对“动态集合”中的状态产生了匹配(dest[nMatched]='*'),nMathed++.
(3)对动态状态机集合中的状态,一但不能匹配(dest[nMatched]!='*')，删除这个状态.
(4)当出现完整匹配时，出现: nMatched == strlen(dest); 就发现了目的节点的一个字符串。生成节点，删除所有动态集合的状态（如果优先匹配短的，否则。。。）

如下：
初始动态状态机集合为空：
输入a后
动态状态机集合:
1: {dest="abcde", nMatched=1};
输入b后
动态状态机集合:
1: {dest="abcde", nMatched=2};
输入c后
动态状态机集合:
1: {dest="abcde", nMatched=3};
.... ...

[ 本帖最后由 cuichaox 于 2008-1-14 12:58 编辑 ]

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)