hdu 3068(最长回文)
题意:容易理解...
思路：可以用扩展kmp来做，但是我还没怎么弄懂，时间复杂度O(n*logn),而manacher算法，第一次听说，代码比较短，不难理解，和扩展kmp有点类似，时间复杂度为：O(n)，所以manacher算法更好吧！学习这个算法我推荐一个好的博客：http://blog.csdn.net/kg_second/article/details/8865210
代码实现：
#include<iostream> #include<string.h> using namespace std; char str1[110010],str2[110010*2]; int n,a[110010*2]; int min(int x,int y) { return x>y?y:x; } void bian(int len) { int i; n=1; str2[0]='$'; for(i=0;i<len;i++) { str2[n++]='#'; str2[n++]=str1[i]; } str2[n]='#'; } int solve() { int max=-1; int i,k,p=0; for(i=1;i<n;i++) { if(i<p) a[i]=min(a[k*2-i],p-i); else a[i]=1; for(;str2[i+a[i]]==str2[i-a[i]];a[i]++) ; if(i+a[i]>p) { k=i; p=i+a[i]; } if(max<a[i]) max=a[i]; } return max; } int main() { int len,max; while(scanf("%s",str1)!=EOF) { len=strlen(str1); getchar(); bian(len); max=solve(); printf("%d\n",max-1); } return 0; }优质内容筛选与推荐>>
1、ioctl和unlock_ioctl的区别
2、超算结课小结
3、解决asp.net向mysql中插入数据的问题
4、StringBuilder , Hashtable
5、破解Wi-Fi密码