Jzoj4889 最长公共回文子序列

最新推荐文章于 2024-09-13 21:47:44 发布

扩展的灰

最新推荐文章于 2024-09-13 21:47:44 发布

阅读量604

点赞数 2

分类专栏： OI 求解策略 ----搜索/暴力/剪枝 ----动态规划 --------序列形dp Jzoj 文章标签：暴力动态规划扩展的灰

本文链接：https://blog.csdn.net/JacaJava/article/details/78419301

版权

OI 同时被 3 个专栏收录

321 篇文章

订阅专栏

Jzoj

227 篇文章

订阅专栏

求解策略

153 篇文章

订阅专栏

YJC最近在学习字符串的有关知识。今天，他遇到了这么一个概念：最长公共回文子序列。一个序列S，如果S是回文的且分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共回文子序列。YJC很聪明，他很快就学会了如何求最长公共回文子序列。他现在想把问题规模扩大一些，于是他提出了这么一个问题：给一个长度为n(1≤n≤100000)的字符串a和一个长度为m(1≤m≤20)的字符串b，求a和b的最长公共回文子序列的长度。YJC发现他不会做了，于是他来问你这个问题的答案。

以后写题解都开大字体

嗯，看到数据范围发现可以做呢

枚举b每一个子序列并在A中匹配，复杂度2^m*n

明显T，怎么加速匹配呢？

~~一个SAM不就行了嘛~~

这个可是子序列，搞一个数组就可以了，存下每个字符的位置让后二分就好了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[100010],b[30];
int f[26][100010]={0},t[26]={0},n,m;
int w[30],c=0,ans=0;
bool ok(int x){
	for(int i=c=0;x;i++,x>>=1) if(x&1) w[c++]=i;
	for(int i=0;(i<<1)<c;++i) if(b[w[i]]!=b[w[c-i-1]]) return 0;
}
int cal(){
	int pos=-1;
	for(int i=0;i<c;++i){
		int j=b[w[i]]-'a',l=0,r=t[j];
		for(int M;l<r;){
			M=l+r>>1;
			if(f[j][M]<=pos) l=M+1;
			else r=M;
		}
		if(l==t[j]) return 0;
		pos=f[j][l];
	}
	return c;
}
int main(){
	freopen("lcps.in","r",stdin);
	freopen("lcps.out","w",stdout);
	scanf("%s%s",a,b);
	n=strlen(b); m=strlen(a);
	for(int i=0;i<m;++i)
		f[a[i]-'a'][t[a[i]-'a']++]=i;
	for(int i=0;i<26;++i) f[i][t[i]]=m+1;
	for(int i=1;i<(1<<n);++i)
		if(ok(i)) ans=max(ans,cal());
	printf("%d\n",ans);
}