点击打开链接hdu 4300
思路:kmp+next数组的应用
分析:
1 题目要求的是给定一个不完整的由n个字符构成的字符串并且字符串有密文和明文两部分组成,现在要求完整的字符串。
2 很明显密文的长度不确定,现在又要求最短的字符串长度。由于在完整的字符串中密文和明文的长度是一样的,那么输入的字符串中至少有(n+1)/2是密文,所以我们假设密文后面的都是明文,那么我们将这些明文转化为密文后求next数组就可以知道前缀和后缀的最大的匹配数,那么如果匹配数越大就说明总的串的长度就越小。
3 但是有个地方需要注意,输入的字符串长度为n,那么至少(n+1)/2为密文,那么明文最多为tmp = n-(n+1)/2,所以next[n]的最大值是不能超过tmp的,如果超过了那么就另next[len] = tmp即可,说明已经最大了。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100010
#define N 30
int t;
int next[MAXN];
char mp[N];
char pattern[MAXN];
/**求最大的匹配数*/
void getNext(){
int len = strlen(pattern);
next[0] = next[1] = 0;
for(int i = 1 ; i < len ; i++){
int j = next[i];
while(j && pattern[i] != pattern[j])
j = next[j];
next[i+1] = pattern[i] == pattern[j] ? j+1 : 0;
}
}
int main(){
char str[MAXN];
scanf("%d" , &t);
while(t--){
scanf("%s" , mp);
scanf("%s" , pattern);
int len = strlen(pattern);
/*求最大的匹配数*/
memcpy(str , pattern , sizeof(pattern));
for(int i = (len+1)/2 ; i < len ; i++){
int num = pattern[i]-'a';
pattern[i] = mp[num];
}
getNext();
/*当最大匹配数超过(len-(len+1)/2)的是就要直接把next[len] = len-(len+1)/2*/
if(next[len] > (len-(len+1)/2))
next[len] = len-(len+1)/2;
int num = len-next[len];
printf("%s" , str);
/*输出剩下的明文*/
int j = num-next[len];
int i = num-j;
/*把密文转化为明文*/
for(; i < num ; i++){
for(int j = 0 ; j < 26 ; j++){
if(str[i] == mp[j]){
printf("%c" , j+'a');
break;
}
}
}
printf("\n");
}
return 0;
}
利用kmp的扩展
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
#define N 30
int t;
int next[MAXN];
int extend[MAXN];
char mp[N];
char text[MAXN];
char pattern[MAXN];
/*求扩展kmp的next*/
void getNext(){
int len = strlen(pattern);
int a = 0;
next[0] = len;
while(a < len-1 && pattern[a] == pattern[a+1])
a++;
next[1] = a;
a = 1;/*a重新赋值为1*/
for(int k = 2 ; k < len ; k++){
int p = a+next[a]-1;
int l = next[k-a];
if(k+l-1 >= p){
int j = max(p-k+1 , 0);
while(k+j < len && pattern[k+j] == pattern[j])
j++;
next[k] = j;
a = k;
}
else
next[k] = l;
}
}
/*求estend数组*/
void getExtend(){
int n = strlen(text);
int m = strlen(pattern);
int a = 0;
int minLen = min(n , m);
while(a < minLen && text[a] == pattern[a])
a++;
extend[0] = a;
a = 0;
for(int k = 1 ; k < n ; k++){
int p = a+extend[a]-1;
int l = next[k-a];
if(k-1+l >= p){
int j = max((p-k+1) , 0);
while(k+j < n && j < m && text[k+j] == pattern[j])
j++;
extend[k] = j;
a = k;
}
else
extend[k] = l;
}
}
int main(){
char str[MAXN];
int max;
scanf("%d" , &t);
while(t--){
scanf("%s" , mp);
scanf("%s" , pattern);
int len = strlen(pattern);
memcpy(str , pattern , sizeof(pattern));
/*求出模式串*/
int pos = 0;
memset(text , '\0' , sizeof(text));
for(int i = (len+1)/2 ; i < len ; i++){
int num = pattern[i]-'a';
text[pos++] = mp[num];
}
pattern[(len+1)/2] = '\0';
/*求next数组*/
getNext();
/*求extend数组*/
getExtend();
/*求最长的公共前缀数*/
int max = 0;
for(int i = 0 ; i < pos ; i++){
if(max < extend[i] && extend[i]+i == pos)
max = extend[i];
}
/*输出*/
printf("%s" , str);
int cir = len-max;/*求出密文的长度*/
int j = cir-max;
int i = cir-j;/*求出要输出的起始位置*/
for(; i < cir ; i++){
for(int j = 0 ; j < 26 ; j++){
if(str[i] == mp[j]){
printf("%c" , j+'a');
break;
}
}
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU图论题目分类