点击打开链接hdu 1238
思路:kmp+暴力枚举子串
分析:
1 题目要求找到一个子串x,满足x或x的逆串是输入的n个字符串的子串,求最大的x,输出x的长度
2 题目的n最大100,每一个字符串的最大长度为100,那么暴力枚举子串就是o(n^2)才10000肯定是不会超时的,但是由于这里涉及到了逆串的问题,所以我们应该还要求出n个子串的逆串,然后在求最大的x。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
int t , n;
char words[MAXN*2][MAXN];
int next[MAXN];
/*qsort按照长度排序*/
int cmp(const void *str1 , const void *str2){
return strlen((char*)str1)-strlen((char*)str2);
}
/*求反转字符串*/
void init(){
for(int i = 0 ; i < n ; i++){
int pos = 0;
for(int j = strlen(words[i])-1 ; j >= 0 ; j--)
words[i+n][pos++] = words[i][j];
words[i+n][pos] = '\0';
}
}
/*求next数组*/
void getNext(char *str){
int len = strlen(str);
next[0] = next[1] = 0;
for(int i = 1 ; i < len ; i++){
int j = next[i];
while(j && str[i] != str[j])
j = next[j];
next[i+1] = str[i] == str[j] ? j+1 : 0;
}
}
/*匹配函数*/
bool find(char *words , char *str){
int len = strlen(words);
int m = strlen(str);
int j = 0;
for(int i = 0 ; i < len ; i++){
while(j && words[i] != str[j])
j = next[j];
if(words[i] == str[j])
j++;
if(j == m)/*找到了就return true*/
return true;
}
return false;
}
int main(){
char max[MAXN];
scanf("%d" , &t);
while(t--){
scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
scanf("%s" , words[i]);
/*排序*/
qsort(words , n , sizeof(words[0]) , cmp);
/*反转字符串*/
init();
char tmp[MAXN];
int pos;
int len = strlen(words[0]);
memset(max , '\0' , sizeof(max));
/*枚举正向的子串*/
for(int i = 0 ; i < len ; i++){
pos = 0;
memset(tmp , '\0' , sizeof(tmp));
for(int j = i ; j < len ; j++){
tmp[pos++] = words[0][j];
getNext(tmp);
int vis = 1;
for(int k = 1 ; k < n ; k++){
if(!find(words[k] , tmp) && !find(words[k+n] , tmp)){
vis = 0;
break;
}
}
if(vis && strcmp(max , tmp) < 0)
memcpy(max , tmp , sizeof(tmp));
}
}
/*枚举反向的子串*/
for(int i = 0 ; i < len ; i++){
pos = 0;
memset(tmp , '\0' , sizeof(tmp));
for(int j = i ; j < len ; j++){
tmp[pos++] = words[n][j];
getNext(tmp);
int vis = 1;
for(int k = 0 ; k < n ; k++){
if(!find(words[k] , tmp) && !find(words[k+n] , tmp)){
vis = 0;
break;
}
}
if(vis && strcmp(max , tmp) < 0)
memcpy(max , tmp , sizeof(tmp));
}
}
printf("%d\n" , strlen(max));/*输出长度*/
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
自己做的HDU ACM已经AC的题目
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU图论题目分类
hdu 1005.比较简单的一道题,有兴趣的可以看看。