首页 > 代码库 > 【编程之美】3.5 最短摘要的生成
【编程之美】3.5 最短摘要的生成
题目：有搜索后的网页分词序列 数组W 其中W[0]、W[1]、...W[N]为分好的词。
用户输入的关键词为数组 Q 其中Q[0]、Q[1]...Q[M]为搜索的关键词。
找到W中最小的范围W[i]~W[j]让其包括所有的Q。
思路：
最想当然的思路就是从W[0]开始，对每个Q遍历判断有没有一样的，截取出第一个包含Q中元素的W[i]到最后一个包括Q中元素的W[j]。需要O(MN)次比较。
如果前提能够肯定W中包含所有的Q那就，先从W[0]开始找到第一个包含Q的，再从W[N-1]向前找第一个包含Q的。
上面的思路有问题，因为W中可能重复的包含了Q中的元素，我们找最短的是要W[i-j]中没有重复的Q元素
为了去掉重复的数字，就先找到一个全部包含Q的范围，然后去掉第一个元素，再找包含全部Q的范围，依次类推。记录下最短的范围。就是答案中的解法二。解法二的伪代码如下：
注意其中对头和尾分别使用了两个指针。
int nTargetLen = N + 1;int pBegin = 0;int pEnd = 0;int nLen = N;int nAbstractBegin = 0;int nAbstractEnd = 0;while (true){ while(!isAllExisted() && pEnd < nLen) { pEnd++; } while(isAllExisted()) { if(pEnd - pBegin < nTargetLen) { nTargetLen = pEnd - pBegin; nAbstractBegin = pBegin; nAbstractEnd = pEnd - 1; } pBegin++; } if(pEnd >= N) Break;}
自己还想了一种，就是先把W中所有与Q相同的都先记下来位置，然后用图的方法找经过所有节点的最小路径。但是由于解法二已经是O(MN)了,用图的话，光记录位置就要O(MN)划不来，就没做了。
【编程之美】3.5 最短摘要的生成
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。