#include<iostream> #include<string> #include<vector> using namespace std; int main() { string str1, str2; while (getline(cin, str1),getline(cin,str2)) { int max = 0; vector<vector<int>> dp(str1.size(),vector<int>(str2.size(),0)); for (int i = 0; i < str1.size(); i++) { for (int j = 0; j < str2.size(); j++) { if (str1[i] == str2[j]) if (i == 0 || j == 0) dp[i][j] = 1; else dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j]>max) max = dp[i][j]; } } cout << max << endl; } return 0; }
#include<iostream>#include<string>#include<vector>using namespace std;int solve(string& A, string& B){int res = 0,n = B.size();vector<vector<int> > dp(A.size() + 1);for(int i = 0;i < A.size() + 1;i++)dp[i].resize(n + 1);for(int i = 1;i <= A.size();i++){for(int j = 1; j <= n; j++){if(A[i - 1] == B[j - 1])res = max(res,dp[i][j] = dp[i - 1][j - 1] + 1);}}return res;}int main(){string A, B;getline(cin, A);getline(cin, B);cout << solve(A, B) << endl;return0;}
int LongestSubstr(string A,string B) { vector<int> dp(A.size() + 1); int res = 0; for (int i = 1; i <= A.size(); i++) { for (int j = 1; j <= B.size(); j++) { if (A[i - 1] == B[i - 1]) res = max(res, dp[j] = dp[j - 1] + 1); } } return res; }
int LongestSubstr(string A,string B) { int res = 0, len = 0, flag = 0; for (int i = 1; i <= A.size(); i++) { for (int j = 1; j <= B.size(); j++) { if (A[i - 1] == B[j - 1]) res = max(res, len += 1), flag = 1; } if (!flag) len = 0; flag = 0; } return res; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str1; while((str1 = br.readLine()) != null){ String str2 = br.readLine(); System.out.println(solve(str1, str2)); } } private static int solve(String str1, String str2) { int m = str1.length(); int n = str2.length(); // dp[i][j]是字符串str1.substring(0, i)和str2.substring(0, j)的最大公共子串的长度 int[][] dp = new int[m + 1][n + 1]; int result = 0; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ dp[i][j] = str1.charAt(i - 1) == str2.charAt(j - 1)? dp[i - 1][j - 1] + 1: 0; result = Math.max(result, dp[i][j]); } } return result; } }
//dp二维转一维,做法类似于第二题思路 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = sc.nextLine(); String b = sc.nextLine(); int[] dp=new int[b.length()+1]; for(int i=0;i<dp.length;i++) { dp[i]=0; } int res=0,index=1; for(int i=0;i<a.length();i++) { for(int j=index;j<dp.length;j++) { if(a.charAt(i)==b.charAt(j-1)) { dp[j]+=dp[j-1]+1; res=Math.max(res, dp[j]); index=++j; break; }else{ for(int k=1;k<b.length();k++) { dp[k]=0; } index=1; } } } System.out.println(res); } }
// 一个串在另一个串上从尾部进入直到串头滑出为止,时间复杂度为O(N^2)的.
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int main(){ char str1[51],str2[51]; int lmax,l; while(fgets(str1,51,stdin)!=NULL){ fgets(str2,51,stdin); int l1=0; int l2=0; while(str1[l1]!='\n'&&str1[l1]!='\0'){l1++;} while(str2[l2]!='\n'&&str2[l2]!='\0'){l2++;} lmax=0; // from front to back for(int i=0;i<l1;i++){ int ii=i; int cnt=0; int size(i+1,l2); l=0; for(int j=l2-1;cnt<size;j--,ii--,cnt++){ if(str1[ii]==str2[j])l+=1; else l=0; if(l>lmax)lmax=l; } } // from back to front for(int i=0;i<l2;i++){ int ii=i; int cnt=0; int size(i+1,l1); l=0; for(int j=l1-1;cnt<size;j--,ii--,cnt++){ if(str2[ii]==str1[j])l+=1; else l=0; if(l>lmax)lmax=l; } } // output result cout<<lmax<<endl; } return 0; } 添加笔记
思路: 准备一个N+1 * N+1大小的二维数组dp,置0。 dp[i][j]代表s1的0-i位置与s2的0-j位置中连续公共子串的最大长度。 则有: 如果s1[i] == s2[j],dp[i][j] = dp[i-1][j-1] + 1; 否则,dp[i][j] = 0; 记录最大长度即可。 C++源码: #include <iostream> #include <string.h> using namespace std; #define MAX_LENGTH 50 int main(){ string s1, s2; getline(cin, s1); getline(cin, s2); int len1 = s1.size(); int len2 = s2.size(); int maxLength = 0; int dp[MAX_LENGTH+1][MAX_LENGTH+1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= len1; i++){ for (int j = 1; j <= len2; j++){ if (s1[i-1] == s2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; if (dp[i][j] > maxLength) maxLength = dp[i][j]; }else{ dp[i][j] = 0; } } } cout << maxLength << endl; return 0; }
#include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int main(){ string s1, s2; while (getline(cin, s1), getline(cin, s2)){ int l1 = s1.size(); int l2 = s2.size(); vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0)); int result = 0; for (int i = 1; i <= l1; i++){ for (int j = 1; j <= l2; j++){ if (s1[i - 1] == s2[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + 1; result = max(dp[i][j], result); } else{ dp[i][j] = 0; } } } cout << result << endl; } return 0; }
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String s1 = sc.nextLine(); String s2 = sc.nextLine(); int l1 = s1.length(); int l2 = s2.length(); int result = 0; int[][] dp = new int[l1 + 1][l2 + 1]; for (int i = 1; i <= l1; i++){ for (int j = 1; j <= l2; j++){ if (s1.charAt(i - 1) == s2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1] + 1; result = Math.max(dp[i][j], result); } else{ dp[i][j] = 0; } } } System.out.println(result); } sc.close(); } }
var str1 = readline(); var str2 = readline(); var arr = []; for (var i = 0; i < str1.length; i++) { arr[i] = []; for (var j = 0; j < str2.length; j++) { arr[[i]][j] = 0; } } var max = 0; for(var i=0;i<str1.length;i++){ for (var j = 0; j < str2.length; j++) { if (str1[i] == str2[j]) { if(i==0 || j==0){ arr[i][j] = 1; }else{ arr[i][j] = arr[i-1][j-1] + 1; } } if(arr[i][j]>max){ max = arr[i][j]; } } } print(max);
#include<iostream>#include<string>using namespace std;#define N 51int main(){string s1, s2;getline(cin, s1);getline(cin, s2);intdp[N][N]={0};if(!s1.length() || !s2.length())return -1;int maxLength = 0;for(int i=0; i<s1.length(); ++i){for(int j=0; j<s2.length(); ++j){if(s2[j]==s1[i])dp[i+1][j+1] = dp[i][j]+1;elsedp[i+1][j+1] = 0;if(maxLength<dp[i+1][j+1])maxLength = dp[i+1][j+1];}}cout<<maxLength<<endl;return 0;}
#include<string> #include<iostream> #include<algorithm> using namespace std; int dp[55][55],Max=0,i,j; int main(){ string x,y; getline(cin,x);getline(cin,y); for(i=1;i<=x.length();i++) for(j=1;j<=y.length();j++){ if(x[i-1]==y[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=0; Max=max(Max,dp[i][j]); } printf("%d\n",Max); }
#按照小的字符串顺序和逆序各遍历一遍取最大值str1 = raw_input()str2 = raw_input()iflen(str1) > len(str2):str1,str2 = str2,str1res = 0start = 0fori in range(1,len(str1)+1):ifstr1[start:i] in str2:res = max(res,i-start)else:start = iend = len(str1)fori in range(len(str1)-1,0,-1):ifstr1[i:end] in str2:res = max(res,end - i)else:end = iprint res
#include <iostream> #include <vector> #include <string> #include <cstring> #include <map> #include <cmath> using namespace std; int main(){ string s1,s2; getline(cin,s1); getline(cin,s2); int dp[55][55]; memset(dp,0,sizeof(dp)); int ans=0; for (int i = 1; i <= s1.size(); ++i) { for (int j = 1; j <= s2.size(); ++j) { int a=s1[i-1],b=s2[j-1]; if(a==b){ dp[i][j]=dp[i-1][j-1]+1; ans=max(ans,dp[i][j]); } } } cout<<ans<<endl; return 0; }
[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串
这道题其实我以前做过,但是这次碰到却一直想不起来,非常难受,交卷后看评论里的动态规划就立马明白了,下面是代码。
stream特性是真的好用,一旦拥有,爱不释手。
import java.util.Arrays; import java.util.Scanner; public class Main { int max=0; public static void main(String[] args){ Main s=new Main(); Scanner in=new Scanner(System.in); String s1=in.nextLine(); String s2=in.nextLine(); int len1=s1.length(); int len2=s2.length(); int dp[]=new int[len2+1]; for (int i=1;i<=len1;i++){ for(int j=len2;j>=1;j--){ if (s1.charAt(i-1)==s2.charAt(j-1)){ dp[j]=dp[j-1]+1; }else{ dp[j]=0; } } int cur = Arrays.stream(dp).max().getAsInt(); if (cur>s.max) s.max=cur; } System.out.println(s.max); } }
#include<bits/stdc++.h> using namespace std; (1154)#define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++) #define per(i,a,b) for(int i = (int)b;i>=(int)a;i--) (3710)#define pb push_back #define mp map_pair (3711)#define all(x) (x).begin(),(x).end() #define fi first (3473)#define se second #define SZ(x) ((int)(x).size()) const int maxn=10050; typedef long long ll; const double pi = acos(-1.0);//pi const ll mod=1000000007; const int N=2e5+10,inf=0x3f3f3f3f; int sa[N]; int rk[N]; int tmp[N]; int lcp[N]; char s[N],t[N]; int n,k; bool cmp(int i,int j){ if(rk[i] != rk[j]) return rk[i]<rk[j]; else { int ri=i+k<=n?rk[i+k]:-1; int rj=j+k<=n?rk[j+k]:-1; return ri<rj; } } void build(char *s,int *sa) { n=strlen(s); for(int i=0;i<=n;i++){ sa[i]=i; rk[i]=i<n?s[i]:-1; } for(k=1;k<=n;k*=2){ sort(sa,sa+n+1,cmp); tmp[sa[0]]=0; for(int i=1;i<=n;i++){ tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0); } for(int i=0;i<=n;i++){ rk[i]=tmp[i]; } } } void LCP(char *s,int *sa,int *lcp){ n=strlen(s); for(int i=0;i<=n;i++) rk[sa[i]]=i; int h=0; lcp[0]=0; for(int i=0;i<n;i++){ int j=sa[rk[i]-1]; for (h ? h-- : 0; j + h < n&&i + h < n&&s[j + h] == s[i + h]; h++); lcp[rk[i]-1] = h; } } int belong[maxn]; int main(){ gets(s); n=strlen(s); for(int i=0;i<n;i++) belong[i]=1; s[n++]='{'; gets(s+n); //printf("%s",s); int now=n; n=strlen(s); for(int i=now;i<n;i++) belong[i]=2; build(s,sa); LCP(s,sa,lcp); int ans=0; //for(int i=0;i<n;i++) printf("%d ",lcp[i]); //printf("\n"); for(int i=2;i<=n;i++){ if(belong[sa[i-1]]+belong[sa[i]]==3){ ans=max(ans,lcp[i-1]); } } printf("%d\n",ans); return 0; } /* */
#include<bits/stdc++.h> using namespace std; int res = 0; int dp(string A, string B){ int size1 = A.length(); int size2 = B.length(); vector<vector<int>> dp(size1+1, vector<int>(size2+1,0)); for(int i = 1; i <= size1; i++){ for(int j = 1; j <= size2; j++){ if(A[i-1] == B[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; } if(dp[i][j] != 0 &&dp[i][j] > res) res = dp[i][j]; } } return res; } int main(){ string A, B; while(getline(cin, A), getline(cin, B)){ int res = dp(A, B); cout << res << endl; } return 0; }