Powered by:NEFU AB-IN
Link
HJ65 查找两个字符串a,b中的最长公共子串
-
题意
查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。
-
思路
参考这篇我之前写的文章 blog,使用字符串哈希和二分实现的
这里用dp实现:
- f[i][j]表示 1~ai,1~bj且ai,bj为结尾的所有公共子串
- 属性:最长公共串长度
- 转移:
- 如果ai==bj且ai,bj都是字母,则f[i][j]=f[i-1][j-1]+1
- 其他,f[i][j]=0
优化:类似01背包问题,考虑i: 1~alen枚举,j: blen~1倒序枚举,即可优化一维文章来源:https://www.toymoban.com/news/detail-702802.html
这里引文要输出较短串中最先出现,所以要先辨别出短的串文章来源地址https://www.toymoban.com/news/detail-702802.html
-
代码
#include <any> #include <bits/stdc++.h> #include <utility> using namespace std; #define int long long #undef int #define SZ(X) ((int)(X).size()) #define ALL(X) (X).begin(), (X).end() #define IOS \ ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) #define DEBUG(X) cout << #X << ": " << X << '\n' typedef pair<int, int> PII; const int N = 1e5 + 10, INF = 0x3f3f3f3f; int dp[N]; signed main() { //freopen("Tests/input_1.txt", "r", stdin); IOS; string a, b; cin >> a >> b; int n = SZ(a), m = SZ(b); if (n > m){ swap(a, b); swap(n, m); } a = " " + a; b = " " + b; int mx = 0, end = -1; for(int i = 1; i <= n; ++ i){ for(int j = m; j >= 1; -- j){ if(a[i] == b[j]){ dp[j] = dp[j - 1] + 1; if(dp[j] > mx){ mx = dp[j]; end = i; } } else dp[j] = 0; } } cout << a.substr(end - mx + 1, mx); return 0; }
到了这里,关于HJ65 查找两个字符串a,b中的最长公共子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!