刚碰上的问题,希望能找到最好的解决方法

welf

有一个链表，节点内容可能是若干个有序字符串的其中一个字符或字符串本身，举个例子，字符串的集合是"abcd","efgh"
链表是a->b->c->d->e->g->h->abcd->efgh.现要对其处理，a->b->c->d能顺序合并成"abcd',e->g->h就不行，应此去掉这三个节点，最后得到的链表是abcd->abcd->efgh.
因为链表巨大，理想的情况是只遍历一趟，尽量不占用额外的空间。

caijimin

如果字符串的集合是预先已知的，应该可以。  否则涉及到回溯，只遍历一遍不大可能。

Nzm

觉得可以分配点空间存储有可能要合并的字符或字符串.这样还是可能一次遍历的.

cuichaox

如果预定义子串中，有“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 编辑 ]