【模拟赛】2021.8.11.B

本文主要是介绍【模拟赛】2021.8.11.B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有两个字符串，求公共最长回文子序列

思路

暴力能过👍
就是枚举b串的回文子串，然后再找是否存在于a串
优化：
查找是否存在于a串时，可以用一个$f_{i,j}$表示a穿第i位以后第一次出现j字符的位置来查找，预处理详见代码👍

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int F[100250][30], cha[30];
int n, m, k, l, Ans;
string s, ss;int Check(string s)
{s = ' ' + s;for(int i = 1, j = s.length() - 1; i <= j; ++i, --j)if(s[i] != s[j])return 0;return 1;
}int Find(string s)
{k = 0, l = 0;while((k || !l) && l <= m)k = F[k][s[l++] - 'a' + 1];if(l > s.length())return 1;return 0; 
}void DFS(int now, string si)
{if(now > m){int len = si.length();if(si == "kgggk")si = "kgggk";if(Check(si) && Find(si))if(Ans < len)Ans = len;return;}DFS(now + 1, si + ss[now]);DFS(now + 1, si);return;
}int main()
{cin >> s >> ss;n = s.length(), m = ss.length();s = ' ' + s, ss = ' ' + ss;memset(cha, 0, sizeof(cha));for(int i = n; i >= 1; --i)//优化{for(int j = 1; j <= 26; ++j)F[i][j] = cha[j];cha[s[i] - 'a' + 1] = i;}for(int i = 1; i <= 26; ++i)F[0][i] = cha[i];DFS(1, "");printf("%d", Ans);return 0;
}

这篇关于【模拟赛】2021.8.11.B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---