#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[5010][5010],dpr[5010]; int main(){ char str1[5010],str2[5010]; scanf("%s %s",str1+1,str2+1); int maxlen=0,maxend=0; int len1=strlen(str1+1); int len2=strlen(str2+1); for(int i=1;i<=len1;++i){ for(int j=1;j<=len2;j++){ if(str1[i]==str2[j]){ dp[i][j]=dp[i-1][j-1]+1; //dp[i][j]表示以i,j为尾的最长公共子串的长度(连续) if(maxlen<dp[i][j]) { maxlen=dp[i][j]; maxend=i; } } } } if (maxlen == 0) { printf("-1"); return 0; } for(int i=maxend-maxlen+1;i<=maxend;i++){ printf("%c",str1[i]); } return 0; //printf("%d",dp[strlen(str1)][strlen(str2)]); }
#include <bits/stdc++.h> using namespace std; int main(){ string a, b; cin>>a>>b; int n=a.length(), m=b.length(); int dp[n+1][m+1], Max=0, l; memset(dp, 0, sizeof(dp)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ if(a[i]==b[j]){ dp[i+1][j+1] = dp[i][j] + 1; if(Max < dp[i+1][j+1]){ Max = dp[i+1][j+1]; l = i+1; } }else dp[i+1][j+1] = 0; } if(Max==0) cout<<-1<<endl; else{ for(int i=l-Max;i<=l-1;i++) cout<<a[i]; } return 0; }
#include<iostream> #include<string> using namespace std; void findLCStr(string A, int n, string B, int m) { int c[n+1][m+1]; int i,j,res=0,res_end;//res 最长公共子串长度,res_end最长公共子串末尾序号 for(i=0;i<=n;i++) c[i][0]=0; for(j=1;j<=m;j++) c[0][j]=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(A[i-1]==B[j-1]){ c[i][j] = c[i-1][j-1] + 1; if(res<c[i][j]){ res = c[i][j]; res_end = i; } //res = max(res, c[i][j]); } else c[i][j] = 0; //与LCS的区别在这里 } } if(res==0) cout<<-1<<endl; else{ for(i=res_end-1-res+1;i<=res_end-1;++i) cout<<A[i]; cout<<endl; } } int main(){ string A,B; cin>>A>>B; findLCStr(A,A.length(),B,B.length()); }
#include <iostream> #include <vector> #include <string> #include <stack>//T6 #include <map> using namespace std; //最长公共子串,dp二维矩阵,dp[i][j] = dp[i-1][j-1],因为要求连续 //搞清楚dp[i][j]的含义 //注意更新maxLen和maxEnd时,要搞清楚dp[i][j] 表示的是以s1[i],s2[j]“结尾”的公共子串的长度 //因此每一个dp[i][j]都要和maxLen比较一下,然后存起来maxLen和maxEnd //矩阵右下角的dp[i][j]代表以s1末尾,s2末尾结尾的公共子串的长度,可以为0,而公共子串不一定非要以s1末尾,s2末尾结尾 int main() { string s1, s2; cin >> s1 >> s2; vector< vector<int>> dp(s1.length(), vector<int>(s2.length(), 0)); for (int j = 0; j < s2.length(); j++) if(s1[0]==s2[j]) dp[0][j] = 1; for (int i = 0; i < s1.length(); i++) if (s1[i] == s2[0]) dp[i][0] = 1; int maxLen = 0, maxEnd = 0; for (int i = 1; i < s1.length(); i++) { for (int j = 1; j < s2.length(); j++) { if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLen) { maxLen = dp[i][j]; maxEnd = i; } } } if (maxLen == 0) { cout << -1; return 0; } else { for (int i = maxEnd - maxLen + 1; i <= maxEnd; i++) cout << s1[i]; } system("pause"); return 0; }
/** ** 后缀自动机模板题,有兴趣可以学一下 ** 可以快速处理一些字符串题 例如 ** 10个长度100000串的最长公共子串 ** 出现次数有限制(比如出现次数为k次)的子串 ** author:XiaKIsGod ** time:2019.9 **/ #include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define pb push_back #define pii pair<int,int> #define mk make_pair #define endl "\n" #define FIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define FIN freopen("1.txt","r",stdin) #define all(x) x.begin(),x.end() #define each(e,v) for(auto e: v) #define debug(a,n) rep(i,0,n) cout<<a[i]<<" ";cout<<endl; #define Time cout<<"Time="<<clock()-start_clock<<"ms"<<endl #define mem(x,v) memset(x,v,sizeof(x)) #define repn(i,a,n) for(int i=a;i<=n;i++) #define rep(i,a,n) for(int i=a;i<n;i++) #define per(i,a,n) for(int i=n-1;i>=a;i--) inline int reads(char s[]){char c;int len = 0;while ((c = getchar()) != ' ' && c!='\n') s[len++] = c;s[len] = 0;return len;} char F[60];template<typename T> inline void write(T x) {if( x < 0 ) putchar( '-' ),x=-x;int cnt = 0 ;while(x) {F[cnt++] = x % 10 + '0' ;x /= 10 ;}while(cnt) putchar(F[--cnt]);putchar(10);} template<typename T> inline void read(T &ret) {char c;ret = 0;T sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret*= sgn;} template<typename T> inline void _max(T &a,const T b){if(a<b) a = b;} template<typename T> inline void _min(T &a,const T b){if(a>b) a = b;} template<typename T> inline void _add(T &a,const T b,const T MOD){a = (a+b)%MOD;} template<typename T> inline T _mul(T a,T b,const T MOD){T ans = 0;while(b){if(b&1) _add(ans,a,MOD);_add(a,a,MOD);b>>=1;}return ans;} template<typename T> inline T _pow(T a,T b,const T MOD){T ans = 1;while(b){if(b&1) ans = _mul(ans,a,MOD);a = _mul(a,a,MOD);b>>=1;}return ans;} using namespace std; const int N = 5010; const int sigma_size = 255; struct Node{ int ch[sigma_size],len,fa; }pool[N<<1]; int last = 1,tot = 1; void extend(int x){ int p = last; int np = last = ++tot; pool[np].len = pool[p].len + 1; for(;p&&!pool[p].ch[x];p = pool[p].fa) pool[p].ch[x] = np; if(!p) pool[np].fa = 1; else{ int q = pool[p].ch[x]; if(pool[q].len==pool[p].len +1) pool[np].fa = q; else{ int nq = ++tot; pool[nq] = pool[q]; pool[nq].len = pool[p].len+1; pool[np].fa = pool[q].fa = nq; for(;p&&pool[p].ch[x]==q;p = pool[p].fa) pool[p].ch[x] = nq; } } } char s1[N],s2[N]; int main(){ #ifndef ONLINE_JUDGE FIN; int start_clock = clock(); #endif char c; int len1 = reads(s1); int len2 = reads(s2); rep(i,0,len1) extend(s1[i]); string ans = ""; int u = 1;string now = ""; rep(i,0,len2){ int p = s2[i]; if(pool[u].ch[p]){ now += s2[i]; u = pool[u].ch[p]; if(now.size()>ans.size()) ans = now; continue; } while(u&&!pool[u].ch[p]) u = pool[u].fa; if(!u){ u = 1;now = ""; }else{ now = now.substr(now.size()-pool[u].len,pool[u].len); now += s2[i]; u = pool[u].ch[p]; if(now.size()>ans.size()) ans = now; } } if(ans.size()==0) cout<<-1<<endl; else cout<<ans<<endl; return 0; }
/* 题目要求额外空间复杂度O(1),就不可以用动态规划了 可以将一个串不动,另一个串在此串上向后滑动,每滑动一格扫描一次重叠部分的最长公共子串 然后两个串互换,再滑一次。 最后取最长公共子串。 */ import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str1 = scanner.nextLine(); String str2 = scanner.nextLine(); int size1 = str1.length(); int size2 = str2.length(); if (size1 == 0 || size2 == 0) { System.out.println("-1"); return; } // 串2不动,串1向后滑动 StringBuilder result = new StringBuilder(); for (int i = 0; i < size2; ++i) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < size1 && i + j < size2; ++j) { if (str2.charAt(i + j) == str1.charAt(j)) { sb.append(str1.charAt(j)); } else { result = result.length() > sb.length() ? result : sb; sb = new StringBuilder(); } } result = result.length() > sb.length() ? result : sb; } // 串1不动,串2向后滑动 for (int i = 0; i < size1; ++i) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < size2 && i + j < size1; ++j) { if (str1.charAt(i + j) == str2.charAt(j)) { sb.append(str2.charAt(j)); } else { result = result.length() > sb.length() ? result : sb; sb = new StringBuilder(); } } result = result.length() > sb.length() ? result : sb; } if (result.length() == 0) { System.out.println("-1"); return; } System.out.println(result); } }
因为计算每一个 的时候只需要计算,所以只要按照斜线方向(遍历 n + m - 1条斜线)计算所有的值,用一个变量维护最大值即可
核心:知道如何遍历 n + m - 1 条斜线(这里从最右上角的斜线开始)
C++ 代码
// 时间复杂度O(nm),空间复杂度O(1) #include <algorithm> #include <iostream> using namespace std; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif string a, b; cin >> a >> b; int n = a.size(), m = b.size(); int len = 0, res = 0; int row = 0, col = m - 1; // 从右上角开始 int lcs_i = 0, lcs_j = 0; // 计算矩阵中的每一条斜线上的值 while (row < n) { int i = row, j = col; // 斜线起点 while (i < n && j < m) { // 遍历当前斜线 if (a[i] == b[j]) { len++; if (len > res) { res = len; lcs_i = i, lcs_j = j; // 记录最大长度子串的最后一个元素(i,j) } } else len = 0; // 断开后,len重新算 i++, j++; } len = 0; // 下一条斜线 len 从 0 开始 // 改变斜线起点 if (col > 0) col--; else row++; } string s; row = lcs_i, col = lcs_j; while (row >= 0 && col >= 0) { if (a[row] == b[col]) s += a[row]; else break; row--, col--; } reverse(s.begin(), s.end()); if (res == 0) cout << -1 << endl; else cout << s << endl; return 0; }
import sys for line in sys.stdin: line = line.strip() if len(line)<=0:break line2 = input().strip() if len(line)>len(line2): long_str = line short_str = line2 else: long_str = line2 short_str = line m,n = len(long_str),len(short_str) max_len = 0 max_res = '' flag = False for left in range(n): i,j = 0,left if flag:break while(i<m): if long_str[i]==short_str[j]: i+=1 j+=1 if j>=n: if j-left+1>max_len: max_len = n-left max_res = short_str[left:] flag = True break else: if j-left+1>max_len: max_len = j-left+1 max_res = short_str[left:j] j = left i+=1 print(max_res) 先来一段暴力超时的代码,就是固定left然后往右遍历,去找最长的子串max_res,学到了更厉害的解法就来
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int m = str1.length();
int n = str2.length();
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for(int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
//二维dp数组,动态规划
int max = 0;
int index = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(ch1[i - 1] == ch2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
dp[i][j] = 0;
}
if(dp[i][j] > max) {
index = i;
max = dp[i][j];
}
}
}
if(max == 0) {
System.out.println(-1);
}else {
String res = str1.substring(index - max, index);
System.out.println(res);
}
}
}
/** * 按对角线走 * 只记录当前位置的i-1,j-1位置即可 * @author zms * @date * @param * @return */ public static String maxSeq(String s1, String s2) { int length1 = s1.length(); int length2 = s2.length(); int max = 0; int posJ = 0; // 上半个矩形的对角线 for (int j = length2 - 1; j >= 0; j--) { int len = 0; int j1 = j; for (int i = 0; i < length1; i++) { if (j1 >= length2) break; if (s1.charAt(i) == s2.charAt(j1)) { len++; if (len > max) { posJ = j1; max = len; } } else { len = 0; } j1++; } } // 下半个矩形的对角线 for (int i = 1; i < length1; i++) { int len = 0; int i1 = i; for (int j = 0; j < length2; j++) { if (i1 >= length1) { break; } if (s1.charAt(i1) == s2.charAt(j)) { len++; if (len > max) { posJ = j; max = len; } } else { len = 0; } i1++; } } String str = ""; str = s2.substring(posJ - max+1, posJ+1); return str.equals("")?"-1":str; }
#include<iostream> #include<string> using namespace std; int main() { string s1, s2; cin >> s1 >> s2; int m = s1.size(); int n = s2.size(); if (m == 0 || n == 0) { cout << "-1" << endl; return 0; } int dp[m][n]; int idx_end_in_s1 = 0; int max_len = 0; for (int i = 0; i < m; i++) { if (s1[i] == s2[0]) dp[i][0] = 1; else dp[i][0] = 0; } for (int i = 0; i < n; i++) { if (s2[i] == s1[0]) dp[0][i] = 1; else dp[0][i] = 0; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (s1[i] != s2[j]) dp[i][j] = 0; else dp[i][j] = dp[i-1][j-1] + 1; } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (dp[i][j] > max_len) { max_len = dp[i][j]; idx_end_in_s1 = i; } } } if (max_len == 0) cout << "-1" << endl; else cout << s1.substr(idx_end_in_s1 - max_len + 1, max_len); return 0; }
#include<iostream> #include<string> using namespace std; int main() { string s1, s2; cin >> s1 >> s2; int m = s1.size(); int n = s2.size(); if (m == 0 || n == 0) { cout << "-1" << endl; return 0; } // idx_end_in_s1记录公共子串最后一个字符在s1中的位置 // max_len公共子串长度。这样就能确定字串 int idx_end_in_s1 = 0; int max_len = 0; for (int k = 0; k < m; k++) { int i = k; int j = 0; int start = 0; while (i >= 0 && i < m && j >= 0 && j < n) { if (s1[i] != s2[j]) start = 0; else { start += 1; if (start > max_len) { max_len = start; idx_end_in_s1 = i; } } i++;j++; } } for (int k = 1; k < n; k++) { int i = 0; int j = k; int start = 0; while (i >= 0 && i < m && j >= 0 && j < n) { if (s1[i] != s2[j]) start = 0; else { start += 1; if (start > max_len) { max_len = start; idx_end_in_s1 = i; } } i++;j++; } } if (max_len == 0) cout << "-1" << endl; else cout << s1.substr(idx_end_in_s1 - max_len + 1, max_len); return 0; }
#include<bits/stdc++.h> using namespace std; int main(){ string str1; string str2; cin>>str1; cin>>str2; int row = 0; int col = str2.size()-1; int max = 0; int end = 0; while(row < (int)str1.size()){ int i = row; int j = col; int len = 0; while(i < (int)str1.size() && j < (int)str2.size()){ if(str1[i]!=str2[j]){ len = 0; }else{ len++; } if(len > max){ end = i; max = len; } i++; j++; } if(col > 0){ col--; }else{ row++; } } if (max == 0) { cout << -1; return 0; }else{ for(int i = end-max+1;i < end+1; i++){ cout<<str1[i]; } } return 0; }
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;
public class TestZiChuan
{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String firstStr=sc.next();
String secondStr=sc.next();
Set<String> resultSet=new HashSet<String>();
Set<String> resultFirst=getSonStr(firstStr);
Set<String> secondFirst=getSonStr(secondStr);
for(String result1:resultFirst){
for(String result2:secondFirst){
if(result1.equals(result2)){
resultSet.add(result1);
}
}
}
String maxStr="";
for(String result:resultSet){
if(result.length()>maxStr.length()){
maxStr=result;
}
}
if(Objects.isNull(maxStr) || maxStr.equals("")){
System.out.println("-1");
}
else{
System.out.println(maxStr);
}
sc.close();
}
public static Set<String> getSonStr(String input){
Set<String> set=new HashSet<String>();
int len=input.length();
String tempStr;
for(int i=0;i<len;i++){
tempStr="";
for(int j=i;j<len;j++){
tempStr=tempStr+input.charAt(j);
set.add(tempStr);
}
}
return set;
}
}