链接:
http://poj.org/problem?id=2541
分析与总结:
做这题估算了下复杂度,觉得无论KMP再怎么快,这题暴力也肯定要超时的。
想了很久也没想出个好办法,于是决定暴力之,但是TLE了....于是就放了几天。之后看了下discuss,这题的正解应该是状态压缩dp,不过目前我还不懂,跪了。
之后百度发现也可以用KMP水过,虽然是因为数据水才过的,不过这种思路很巧妙,值得借鉴!
直接暴力是枚举字符串的后面13个的字母,然后再用KMP匹配,这样的话,就绪要枚举多次,分别是后面的13,12,11....1个字母。但是通过观察可以发现,其实要求的是最长公共后缀! 那么可以把原来的字符串逆序转换一下,就变成了求最长公共前缀!这样只需要求一次,用字符串的前面13个字母和原字符串进行匹配一次就够了!
分析与总结:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1002000;
const int START = 2000;
char T[MAXN];
int f[MAXN];
int n,L;
inline char getFail(char* p,int len){
int n=strlen(p);
f[0]=f[1]=0;
int pos=-1, Max=-1;
for(int i=1; i<n; ++i){
int j=f[i];
while(j && p[i]!=p[j])j=f[j];
f[i+1] = p[i]==p[j]?1+j:0;
if(f[i]==13){
return p[i-f[i]-1];
}
if(Max<f[i])
Max=f[i], pos=i-f[i]-1;
}
if(Max==-1)return '0';
return p[pos];
}
int main(){
while(scanf("%d%d%*c",&n,&L)!=EOF){
char *p;
char *str = T+START;
p=str;
gets(str);
// 逆序转换
int len=strlen(str);
for(int i=0,j=len-1; i<len/2; ++i,--j){
char t=str[i];
str[i] = str[j];
str[j] = t;
}
for(int i=0; i<L; ++i){
*(str-1)=getFail(str,len);
--str;
++len;
}
--p;
while(p>=str){
putchar(*p);
--p;
}
puts("");
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
POJ水题集-----50道左右-----增加自信啊..
北大 POJ的水题解答C++版,请合理使用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj的代码,KMP没什么难度算法易证。
北大POJ水题整合包 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj部分水题代码描述,为初学者提供一些必要的基础
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】
poj分类poj分类poj分类poj分类
poj1007 AC代码 0MS过题写法 不过是个水题 哈哈哈哈
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等