首页 > 代码库 > 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】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。