题目描述

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

数据范围

对于50%的数据，满足1≤n≤100。

对于100%的数据，满足1≤n≤100000，1≤m≤20，字符串只包含小写字母。

分析与演绎

原题所求：A和B的最长公共回文子串。

花费O(2m∗m)来把原题转化为判断B是否是A的子串。

暴力会需要O(n)的费用。

考虑交集优化：

由于A持续不变；

有些A中的字符在B中不用遍历甚至从未出现。

那么给A建立一个自动机：

具体而言，对于每一个位置，预处理出离他最近的’a’~’z’的位置。

那么每次遍历B，只需从A中的自动机跳对应字母就可以了。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="lcps.in";

const char* fout="lcps.out";

const int inf=0x7fffffff;

const int maxn=100007,maxm=23;

int n,m,i,j,k;

char a[maxn],b[maxm],c[maxm];

int pos[maxn][26],last[26];

int judge(int v){

    int i,j,k=0;

    memset(c,0,sizeof(c));

    for (i=1;i<=m;i++)

        if (v&(1<<(i-1))) c[++k]=b[i];

    for (i=1;i<=k/2;i++)

        if (c[i]!=c[k-i+1]) return 0;

    j=0;

    for (i=1;i<=k;i++){

        if (pos[j][c[i]-'a']) j=pos[j][c[i]-'a'];

        else return 0;

    }

    return k;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%s",a+1);

    scanf("%s",b+1);

    n=strlen(a+1);

    m=strlen(b+1);

    for (i=n;i>=0;i--){

        for (j=0;j<26;j++){

            pos[i][j]=last[j];

        }

        if (i) last[a[i]-'a']=i;

    }

    int ans=0;

    for (i=(1<<m)-1;i>=0;i--) if (j=judge(i)) ans=max(j,ans);

    printf("%d\n",ans);

    return 0;

}