最长回文子序列的两种解法

回文子序列的两种解法"/>

最长回文子序列的两种解法

最长回文子序列的两种解法

给个交题的链接-----acwing
/

法一：
哈希表+二分查找

//水平有限，很多讲不清楚的，建议动手画一画（dog）
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;typedef unsigned long long ULL;
const int maxn=2000010,P=131; //数组开最大长度的两倍，因为下文要插入特殊字符
ULL hl[maxn],hr[maxn],p[maxn];
char str[maxn];ULL get(ULL h[],int l,int r)
{return h[r]-h[l-1]*p[r-l+1];
}int main()
{int t=1;while(cin>>str+1,strcmp("END",str+1))//只有逗号后面的返回值有效{int n=strlen(str+1);for(int i=2*n;i>0;i-=2){str[i]=str[i/2];str[i-1]='z'+1;}n*=2;   //插入特殊字符后n变为2np[0]=1;for(int i=1,j=n;i<=n;i++,j--){p[i]=P*p[i-1];hl[i]=hl[i-1]*P+str[i]-'a'+1; //正序哈希表计算，表示前i位的哈希值，其中下标小的一侧作为哈希值高位hr[i]=hr[i-1]*P+str[j]-'a'+1; //倒序哈希表计算，表示后i位的哈希值，其中下标大的一侧作为哈希值高位}int res=0;for(int i=1;i<=n;i++){int l=0,r=min(i-1,n-i);//对半径的长度二分，l和r为以str[i]为中心的半径最大最小值while(l<r){int mid=(l+r+1)>>1;if(get(hl,i-mid,i-1)!=get(hr,n+1-(i+mid),n+1-(i+1))) r=mid-1;//第一个get取以str[i]为中心，以mid为半径，左侧的哈希值，第二个get取右侧哈希值（正序的哈希值）//第二个get通过(n+1)-x将x映射到正序else l=mid;}//判断插入的特殊字符的情况，对应不同取最大值的情况if(str[i-l]<='z')res=max(res,l+1);else res=max(res,l);}printf("Case %d: %d\n",t++,res);}
}

法二
马拉车算法
挖个坑，先学、、、、