文本中包含多个关键词的最小区间

一篇文章，切完词之后放到一个vector中，一个查询切完词也放到一个vector中，写一个函数找出这篇文章中包含这个查询中所有词的最小区间的i和j。只要返回第一个即可。

这是一个很有实用价值的题目。在搜索引擎中，我们如果搜索了几个关键字，那么在搜索结果中每个条目，都会显示包含所有关键字的一段很短的文字的summary.

这个题看到稍微分析了下就感觉和首尾相连的珠子的那道题类似。

http://blog.chinaunix.net/uid-26456800-id-3380219.html

假设有k个关键字，文本长度是n,那么最后算法复杂度是 O(nk).

解析：

a.假设有文本text,长度为len,有K个关键字存储在数组keys[K]

b.我们用函数f(n,k) 来表示从文本text中下标为n处开始，keys[k]这个关键字结束的位置的下一个.如果找不到，记录为-1.

           例如test = "abcab",keys[2] = "ab" 

           那么有f(0,2) = 2; f(1,2) = 5; f (2,2) = 5 ....

c.那么，从text的位置n开始，覆盖所有关键字的一段，其截至位置

           g(n) =   max{f(n,0), f(n,1)... f(n,K)} ;

 

我们从0～ len-1全部循环，就可以得出从每个位置开始，向后延伸，覆盖所有关键字的最短文本截至的位置。

再从中输出最短的一段即可。

优化：

在b步骤，我们可以直接使用strstr函数，但是这里，f(0,2) = 2, f(1,2) =5算出这两个的时候，显然我们就不用strstr就可以知道 f(2,2) f(3,2) 的值必定都为5.

在c步骤，我们从0~ len-1循环，如果某个位置t开始，有关键字m， 使得f(t,m) = -1,说明从t位置之后，关键字m就不再出现了，所有再往后，就不可能出现覆盖所有关键字的循环了。这时，可以直接跳出。

代码：

因为感觉比较麻烦，这个代码没有实现第一个优化。

/*
 * =====================================================================================
 *
 * Filename: summary.c
 *
 * Description:
 *
 * Version: 1.0
 * Created: 11/01/2012 09:20:25 PM
 * Revision: none
 * Compiler: gcc
 *
 * Author: [e-mail] (),
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MAX 100000
#define KMAX 10
int keysindex[MAX][KMAX];
int result[MAX] = {0};
void Getkeysindex(char* input, char* keys[], int keycount){
    int k = 0;
    for(;k<keycount;k++){
        int i = 0;
        for(;i<strlen(input);i++){
            char *t = strstr(input+i, keys[k]);
            if(t!=NULL){
                keysindex[i][k] = t - input + strlen(keys[k]) -1;
            }
            else{
                keysindex[i][k] = -1;
            }
        }
    }
}
void Match(int keycount, int len){
    int i = 0;
    int k;
    int result[MAX] = {0};
    for(;i<len;i++){
        for(k = 0;k<keycount;k++){
            if(keysindex[i][k] == -1){
                result[i] = -1;
                return;
            }
            result[i] = (result[i] > keysindex[i][k] ? result[i] :keysindex[i][k]);
        }
        printf ( "start: %d end: %d len: %d\n", i, result[i], result[i]-i +1);
    }
}

/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    char *text = "ababcd";
    char *keys[] = {"ab", "bc", "cd"};
    Getkeysindex(text,keys,sizeof(keys)/sizeof(void*));
    Match(sizeof(keys)/sizeof(void*),strlen(text));
    return EXIT_SUCCESS;
}                /* ---------- end of function main ---------- */