动态规划(poj2138):Travel Games最长扩展串

给定一个字符串集作为字典，例如{"cal","calf","calfs","call","calls","choral","chorale","coal","coral"}
然后给出初始字符串cal.
对于一个字符串，如果在字典中存在一个串，只需要在串内添加一个字符就可以构成，那么我们就扩展该串。
比如对于cal, 可以扩展成calf,call, coal。
求一个给定串，在给定的字典内，最长可以扩展到哪个字符串。
上面给出的数据中，最长的扩展串是chorale.
路径为
cal, coal, coral, choral, chorale
原题地址：


Sample Input

9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral

Sample Output

chorale


解法：
一个串当做一个节点，如果一个串可以扩展成另一个串，那么说明他们之间有一条有向边。那么这道题其实就是求从第一个点开始，能到达的最远的点。类似图的最长路径。
给定字典Dic[MAX];
对于一个长度为n的串s.如果它有扩展串:
      f(s).next为它所有可扩展成的串中， 最终长度最长的那一组中，它下个串的下标。
      f(s).max为它所有可扩展成的串中， 最长能扩展到次数
例如对于cal, 有多个扩展串，calf call coal,根据最后结果，
     f(cal).next为coal在字典中的下标。
     f(cal).max 为chorale的长度。

那么对于一个长度为n-1的串 str, 它的扩展串为extend1,extend2 .. extendp
     f(str).max = max{f(extend1).max, f(extend2).max .... f(extendp).max} + 1;
     f(str).next = ex  ( ex为str扩展串中，f(extend).max最大的那个）

如果没有扩展串，那么f(s).next = -1; f(s).max = 1;
当字典中所有的串都被遍历过一遍，即可找出每个串最后能扩展成的最长的串。

优化：
 可以使用一个几个结构体，将每个串和它的扩展串组织起来。然后对数据进行预处理。这样每次获取扩展串时，只需要从children里取就行了。 复杂度可以减少一个n.
代码中还没实现这个优化。
struct word{
     char* str;
     int   children[MAX];
}

代码：

#include <stdlib.h>
#include <stdio.h>

#define MAXCON 1000
#define MAXLEN 80

int result[MAXCON][2]= {{0}};
int isNext(const char* src, const char *next){
    const char *s = src;
    const char *n = next;
    int couter = 0;
    while((*s || *n) && couter<=1){
        if(*s != *n){
            couter ++;
            n++;
            continue;
        }
        s++;
        n++;
    }
    return couter;
    //if is next result 1
    //else return 0;
}
void test(char* input[], int* lens, int count){
    int len = MAXLEN;
    int i;
    for(;len>=3; len--){
        for(i=0;i<count;i++){
            //tracking the str, whose length is len
            if(lens[i] == len){
                //printf("tracking %s \n", input[i]);
                //record the max len
                int max = 1;
                int next = -1;
                int t = 0;
                for(;t<count;t++){
                //    printf("--- %s \n",input[t]);
                    //if a words length is len+1 then check whether they can join.
                    if(lens[t] == len+1 && isNext(input[i],input[t] )== 1){
                        if(max<(1+result[t][0]) ){
                            max =1+result[t][0];
                            next = t;
                        }
                    }
                }
                result[i][0] = max;
                result[i][1] = next;
                printf("(%d) %s    : next = %d, len = %d\n", i,input[i], next, max);
            }
        }
    }


}

int main(){
    char * input[] ={"cal","calf","calfs","call","calls","choral","chorale","coal","coral"};
    int size = sizeof(input)/sizeof(void*);
    int tar = 0;
    int lens[size] ;
    int i;
    for(i=0; i<size; i++){
        lens[i] = strlen(input[i]);
        printf("len[%d] = %d \n",i, lens[i]);
    }
    test(input, lens, size);
    while(result[tar][1]!=-1)
        tar = result[tar][1];
        printf("%s\n", input[tar]);
    return 0;
}