首页 > 代码库 > 最短摘要问题
最短摘要问题
/*最短摘要问题,给一定字符串序列 wo,w1,w2,w3,op1,w4,op2,w5,op1,w6,w7,op1,op2,指定关键字符串为op1,op2,求包含关键字的最小字符串序列。常见于搜索引擎的分词,op1,op2这里没有顺序,否则就更复杂了,最短序列为op1,op2。思路:(1)第一次扫描要包含全部关键词,送wo扫描到op2,即w0,w1,w2,w3,op1,w4,op2,随后左边逐渐缩小,知道第一次不全包含关键字为止(在扫描时候就记录最短的),即w4,op2.此时移动右面知道第一次包含全部,即w4,op2,w5,op1.随后同理,左边逐渐缩小到又不全部包含关键字即为w5,op1,此时右边继续扩展知道op2出现,即w5,op1,w6,w7,op1,op2,随后左边继续缩小即,op2 ,然后右边向右越界退出。最小为op1,op2*///伪代码如下int nTargetLen=N+1;int pBegin=0;int pEnd=0;int nLen=N;int nAbstractBegin=0;int nAbstractEnd=0;while(true){ while(!isAllExisted()&&pEnd<pLen) pEnd++; while(isAllExisted()) { if(pEnd-pBegin<nTargetLen) { pAbstractBegin=pBegin; nAbstractEnd=pEnd; nTargetLen=pEnd-pBegin; } pBegin++; } if(pEnd>=N) //pEnd最大到N-1,如果到N了说明越界了,结束 break;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。