首页 > 代码库 > 最短摘要问题

最短摘要问题

/*最短摘要问题,给一定字符串序列 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;}