首页 > 代码库 > POJ--1699--Best Sequence【扩展KMP+DFS】

POJ--1699--Best Sequence【扩展KMP+DFS】

链接:http://poj.org/problem?id=1699

题意:给出n个字符串,求他们相连的最小长度,如果首尾字母相同则可以共用相同部分,比如两个串ABCDEF和DEFGHI,他们相连为ABCDEFGHI,最小长度为9,中间的DEF部分共用了。


思路:由于数据量较小,首先对每两个字符串a,b用扩展KMP求出a连在b之后可以共用的长度,用数组B[i][j]表示第j个字符串连接在第i个字符串后面能共用的最大长度。

1.在扩展KMP函数中求子串a和母串b的公共前缀数组ret[i](子串、母串、公共前缀数组,为了理解方便,我就这么叫了),如果此时ret[i]与strlen(b)-i的值相等,说明b串剩下的部分和a串的前strlen(b)-i个字符完全相等,则这个值就是我们需要的值,因为i是从小到大的,所以如果找到符合的strlen(b)-i值,最先出现的这个值一定是最大的,即可返回,如果最后没有找到符合的值,说明没有b串的后缀和a串的前缀相等,则返回0。

2.找完了数组B中所有值之后,考虑到一个字符串最多只能连在一个字符串的后面,并且身后也最多只能连接一个字符串,而且此题数据较小,可以用dfs来枚举,枚举每个串当首串的情况(即它不连在其他串之后),然后dfs枚举每个串连在它身后的情况,找出这之中的最小值,就是我们需要的答案。


#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 10100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define MOD 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

char a[15][25];
int next[MAXN],ret[MAXN];
int b[15][15],vis[15];
int ans,n;
int ExtendKMP(char a[],char b[]){
    int i,j,k;
    int M = strlen(a);
    int N = strlen(b);
    for(j=0;1+j<M&&a[j]==a[1+j];j++);
    next[1] = j;
    k = 1;
    for(i=2;i<M;i++){
        int Len = k + next[k], L = next[i-k];
        if(L<Len-i){
            next[i] = L;
        }
        else{
            for(j=max(0,Len-i);i+j<M&&a[j]==a[i+j];j++);
            next[i] = j;
            k = i;
        }
    }
    for(j=0;j<N&&j<M&&a[j]==b[j];j++);
    if(j==N)    return N;
    ret[0] = j;
    k = 0;
    for(i=1;i<N;i++){
        int Len = k + ret[k], L = next[i-k];
        if(L<Len-i){
            ret[i] = L;
        }
        else{
            for(j=max(0,Len-i);j<M&&i+j<N&&a[j]==b[i+j];j++);
            ret[i] = j;
            k = i;
        }
        if(ret[i]==N-i) return ret[i];
    }
    return 0;
}
void dfs(int x,int tot,int len){
    if(tot==n){
        if(ans>len) ans = len;
        return ;
    }
    if(len>ans) return ;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            vis[i] = 1;
            dfs(i,tot+1,len+strlen(a[i])-b[i][x]);
            vis[i] = 0;
        }
    }
}
int main(){
    int t,i,j;
    scanf("%d",&t);
    while(t--){
        memset(b,0,sizeof(b));
        memset(vis,0,sizeof(vis));
        ans = INF;
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%s",a[i]);
        }
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(i==j)    continue;
                b[j][i] = ExtendKMP(a[i],a[j]);
            }
        }
        for(i=0;i<n;i++){
            vis[i] = 1;
            dfs(i,1,strlen(a[i]));
            vis[i] = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}



POJ--1699--Best Sequence【扩展KMP+DFS】