学步园

题目:

        有一字符串由M个单词组成单词之间有空格隔开（只有空格，没有其他标点符号），有N个关键字，现在要在字符串中找出包含N个关键字（每个关键字至少出现一次，没有说要不要按什么顺序）的最短子串。函数原型：String extractSummary(String description, String[] keywords)

思路:

想了一阵,想出了一个方法,设主串长n 关键字长m 则复杂度大致为nlogm

举个例子说下过程:

例如主串: ab ba ad ba ab ef ba ab ef ad

关键字集合 ab ef ad

则查找过程如下:

起始扫描到ab,ab出现次数加一,start赋值0,此时出现了一个关键字

扫描到ba,发现不是关键字,则跳过

扫描到ad,将ad出现次数加一,将上一次扫描到的关键字ab的next[0]赋值2,此时一共出现了2个关键字

扫描到ba,不是关键字跳过

扫描到ab,将ab出现次数加一,发现start所指的关键字出现了两次,因此start所指关键字是多余的,将start指向的关键字ab出现次数减一,并令start=next[start],重复这个过程直至start所指关键字

只出现一次,

扫描到ef,将next[4]赋值5,此时start=2,将ef出现次数加一,此时发现3个关键字均已出现,判断是否为当前最优解....

扫描ba,不是关键字跳过

扫描ab,将上次出现关键字ef的下一个关键字next[5]赋值7,将ab出现次数加一

扫描ef,将上次出现关键字ab的下一个关键字next[7]赋值8,将ef出现次数加一

扫描ad,将上次出现关键字ef的下一个关键字next[8]赋值9,将ad出现次数加一,发现start所指关键字出现多次,因此将start所指关键字出现次数减一, 利用next数组不断跳转,直至start所指关键字只出现一次为止

根据上面过程,可以得到最优解起始8 长度3

程序如下,没按照给的函数名,直接写在主函数了:

输入:
10
ab ba ad ba ab ef ba ab ef ad
3
ab ef ad

输出
8 3

#include<iostream><br /> using namespace std;</p> <p>char in[100000][20],key[1000][20];</p> <p>bool keychuxian[1000];</p> <p>int keynum,next[100000],everkeynum[1000],minstart,minwords,loca=0,chuxiancishu=0;</p> <p>int search(char *a) //判断输入单词是否为关键字,二分查找<br /> {<br /> int left=0,right=keynum-1,mid;<br /> while(left<=right)<br /> {<br /> mid=(left+right)/2;<br /> if(!strcmp(a,key[mid]))<br /> {<br /> if(!keychuxian[mid])<br /> {<br /> chuxiancishu++;<br /> keychuxian[mid]=true;<br /> }<br /> return mid;<br /> }<br /> if(strcmp(a,key[mid])>0) left=mid+1;<br /> else right=mid-1;<br /> }<br /> return -1;<br /> }</p> <p>int cmp(const void *a,const void *b)<br /> {<br /> return strcmp((char *)a,(char *)b);<br /> }</p> <p>int main()<br /> {<br /> int start=-1,i,j,l,words;</p> <p> cin>>words; //输入单词个数</p> <p> for(i=0;i<words;i++)<br /> cin>>in[i];</p> <p> cin>>keynum; //输入关键词个数<br /> for(i=0;i<keynum;i++) cin>>key[i]; //输入每个关键字</p> <p> qsort(key,keynum,sizeof(char)*20,cmp); //对关键字排序,便于查找</p> <p> memset(next,0,sizeof(int)*100000); //对next初始化<br /> memset(everkeynum,0,sizeof(int)*1000); //对每个单词出现次数初始化<br /> memset(keychuxian,false,sizeof(keychuxian));<br /> minstart=-1; minwords=100000000; //对最短长度初始化</p> <p> for(i=0,l=-1;i<words;i++)<br /> {<br /> j=search(in[i]);<br /> if(j!=-1)<br /> {<br /> if(start==-1) //如果start为-1,则将其指向第一次关键字出现的位置<br /> start=i;<br /> if(l!=-1) //l保存的是上一个关键字下标<br /> next[l]=i;<br /> everkeynum[j]++; //将关键字j的出现次数加1<br /> j=search(in[start]);<br /> while(everkeynum[j]>1) //如果当前区间第一个关键字出现次数大于1,则利用next缩小区间<br /> {<br /> everkeynum[j]--;<br /> start=next[start];<br /> j=search(in[start]);<br /> }<br /> if(chuxiancishu==keynum&&i-start+1<minwords) //如果所有关键字均已出现,判断是否为当前最优解<br /> {<br /> minstart=start;<br /> minwords=i-start+1;<br /> }<br /> l=i;<br /> }<br /> }</p> <p> cout<<minstart+1<<' '<<minwords<<endl; //输出起始位置(0开始)和长度</p> <p>}</p> <p>

证明下上面算法的正确性:

设包含所有关键字的最短区间起始位置start, 终止位置i, 则可以推出如下性质:

1. start所指向的单词一定是关键字.(否则必然能缩短区间长度)

2. start所指向的关键字必然在这个最短区间内只出现一次,(否则区间长度至少还能缩小1)

证明:

当区间末尾扫描到i时,由于[start , i]包含了所有关键字,由于start所指向的关键字只在该区间内出现

一次,因此由"while(everkeynum[j]>1)"循环可知必然会在start处停止,此时会更新以前保存的最短长度,故该方法能找到解.

嫌麻烦直接开了个next数组,呵呵,有点浪费空间,可以用链表实现next数组节省空间....