[编程题]公共字串计算
• 热度指数：29412 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

int getCommonStrLength(char * pFirstStr, char * pSecondStr);

char * pFirstStr //第一个字符串

char * pSecondStr//第二个字符串

##### 输入描述:
`输入两个字符串`

`输出一个整数`

## 输入

```asdfas
werasdfaswer```

## 输出

`6`
```最长公共子串和最长公共子序列。。。傻傻烦不清楚

str1="123ABCD456"  str2 = "ABE12345D"

dp[i][j] -- 表示子串str1[0...i]和子串str[0...j]的最长公共子序列

so，代码如下： //求最长公共子串
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String str1 = "";
String str2 = "";
while(sc.hasNext()){
str1 = sc.next();
str2 = sc.next();
System.out.println(getCommonStrLength(str1, str2));
}
}

public static int getCommonStrLength(String str1, String str2){

int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];

for(int i=0;i<=len1;i++){
for(int j=0;j<=len2;j++){
dp[i][j] = 0;
}
}

for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = 0;	//区别在这儿
}
}
}

int max = 0;
for(int i=0;i<=len1;i++){
for(int j=0;j<=len2;j++){
if(max < dp[i][j])
max = dp[i][j];
}
}

return max;
}
}

//求最长公共子序列 import java.util.Scanner;
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String str1 = "";
String str2 = "";
while(sc.hasNext()){
str1 = sc.next();
str2 = sc.next();
System.out.println(getCommonStrLength(str1, str2));
}
}

public static int getCommonStrLength(String str1, String str2){

int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];

for(int i=0;i<=len1;i++){
for(int j=0;j<=len2;j++){
dp[i][j] = 0;
}
}

for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);	//区别在这儿
}
}
}
return dp[len1][len2];
}
} ```

# python solution:

``````def find_lcsubstr(s1, s2):
m=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]  #生成0矩阵，为方便后续计算，比字符串长度多了一列
mmax=0   #最长匹配的长度
p=0  #最长匹配对应在s1中的最后一位
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i]==s2[j]:
m[i+1][j+1]=m[i][j]+1
if m[i+1][j+1]>mmax:
mmax=m[i+1][j+1]
p=i+1
return mmax   #返回最长子串及其长度

while True:
try:
a,b=input(),input()
print(find_lcsubstr(a,b))
except:
break
``````

```#include<iostream>
#include<vector>
using namespace std;
int main(){
string str1, str2;
while(cin >> str1 >> str2){
int len1 = str1.size();
int len2 = str2.size();
int max = 0;
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for(int i = 1; i <= len1; ++i){
for(int j = 1; j <= len2; ++j){
if(str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > max)
max = dp[i][j];
}
}
cout << max << endl;
}
return 0;
}```

<pre class="prettyprint lang-cpp">用动态规划的思路去做就好了，构造了一个矩阵 w e r a s d f a s e w r a 0 0 0 1 0 0 0 1 0 0 0 0 s 0 0 0 0 2 0 0 0 2 0 0 0 d 0 0 0 0 0 3 0 0 0 0 0 0 除了第一行和第一列其它的只要行列字符不同就为0，相同为左上角+1 之后矩阵中最大的值就为结果 #include <iostream> #include <string.h> #include <stdlib.h> #include <vector> #include<algorithm> using namespace std; int main() { string str1,str2; while(cin>>str1) { cin>>str2; vector<vector<int> > matrix(str1.size(),vector<int>(str2.size())); int max_num=0; for(int i=0;i<str1.size();i++) { for(int j=0;j<str2.size();j++) { if(str1[i]!=str2[j]) matrix[i][j]=0; else if(i==0||j==0) { matrix[i][j]=1; if(max_num<1) max_num=1; } else { matrix[i][j]=matrix[i-1][j-1]+1; if(matrix[i][j]>max_num) max_num=matrix[i][j]; } } } cout<<max_num<<endl; } return 0; } </pre> <div> <br> </div> <br>

```#include <iostream>
#include <string>
using namespace std;
int main()
{
string str1,str2;
int dis=0,t=0;
string tmp;
while(cin>>str1>>str2)
{
int len=str1.length();
for(int i=len;i>1;i--)
{
for(int j=0;j<len;j++)
{
if(i+j<=len)
{
tmp=str1.substr(j,i);
t=str2.find(tmp);
if(t!=-1&&tmp.length()>dis)
dis=tmp.length();

}
}
}
cout<<dis<<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();
String max=s1.length()>=s2.length()?s1:s2;
String min=s1.length()>=s2.length()?s2:s1;
int l=0;
String s="";
for (int i = 0; i < min.length(); i++) {
for (int j = i+1; j <= min.length(); j++) {
if (max.contains(min.substring(i,j)) && j-i>l) {
l=j-i;
s=min.substring(i,j);
}
}
}
System.out.println(s.length());
}
sc.close();
}
}```

find()函数和substr()函数的使用
```#include<iostream>
#include<string>
using namespace std;
int main()
{
string str1,str2;
while(cin>>str1>>str2)
{
int n=0;
for(int i=0;i<str1.size();i++)
{
for(int j=str1.size();j>i;j--)
{
if(str2.find(str1.substr(i,j-i))!=string::npos)
n=n>(j-i)?n:(j-i);
}
}
cout<<n<<endl;
}
return 0;
}```

```//思路:动态规划经典问题，dp[i][j]=dp[i-1][j-1]+1 //if s1[i-1]==s2[j-1] else dp[i][j]=0;
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
int m=s1.length();
int n=s2.length();
int maxLen=0;//保存最大长度
vector<vector<int> >dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
if(s1[i-1]==s2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
maxLen=max(maxLen,dp[i][j]);
}
cout<<maxLen<<endl;

}
return 0;
}```

1、当公共字符串可能长度i固定时，只要发现一处比max_len大时，这层i就可以break了，因为往后再找也是长度i了，所以直接执行下一轮i+1
2、本人在代码中加入flag标志位，当i一定时，执行了一遍公共子串查找都没找到，说明公共子串的长度一定小于当前的i，往后i+1及以后就不用再执行了，所以直接return max_len，就是最后结果了。
```def getCommonStrLength(str1, str2):
if len(str1) < len(str2):
s1, s2 = str1, str2
else:
s1, s2 = str2, str1
max_len = 0
for i in range(1, len(s1) + 1):  # s1字符串分割可能的长度
flag = 0
for j in range(len(s1)):  # s1字符串的游标
if s1[j:i + j] in s2 and i + j <= len(s1):
max_len = i
flag = 1
break
if flag == 0:
return max_len
return max_len

while True:
try:
s1 = input().lower()
s2 = input().lower()
print(getCommonStrLength(s1, s2))
except:
break
```

```while True:
try:
a,b = input().lower(),input().lower()
temp = 0
if not a&nbs***bsp;not b:
print(0)
if len(a) > len(b):
a,b = b,a
for i in range(len(a)-1):
for j in range(i,len(a)):
if a[i:j+1] in b:
if len(a[i:j+1]) > temp:
temp = len(a[i:j+1])
else:
break
print(temp)
except:
break```

```import java.util.Scanner;
public class Main {
public static void compare(String str1, String str2){
String result = "";
for (int i = 1; i < str1.length(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = i-1; j < str1.length(); j++) {
if (str2.contains(sb.append(str1.charAt(j)))){
if (sb.length()>result.length()){
result = sb.toString();
}
}
}
}
System.out.println(result.length());
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
String str1 = sc.next();
String str2 = sc.next();
if (str1.length() <= str2.length()){
compare(str1, str2);
}else {
compare(str2, str1);
}
}
}
}```

```import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
while(in.hasNext()){
String str1=in.next();
String str2=in.next();
if(str1.length()>str2.length()){
String temp=str2;
str2=str1;
str1=temp;
}
int flag=0;
String str3=str1.toUpperCase();
String str4=str2.toUpperCase();
int n=str3.length();
while(n>0&&flag==0){
for(int i=0;i<str1.length()-n+1;i++){
String s=str3.substring(i,i+n);
if(str4.contains(s)){
System.out.println(s.length());
flag=1;
break;
}
}
n--;
}
}
}
}```

### 设置最大值maxlen

```#include<iostream>
#include<string>
using namespace std;

int main()
{
string s1, s2;
while(cin>>s1>>s2)
{
int maxlen = 0;
for(int i = 0; i < s1.size(); i++)
{
for(int j = s1.size(); j > i; j--)
{
if(s2.find(s1.substr(i, j-i)) != -1 && maxlen < j - i)
maxlen = j-i;
}
}
cout<<maxlen<<endl;
}
}```

Python解法：
```while True:
try:
a = input()
b = input()
if len(a)>len(b):
temp = a
a = b
b =temp
str_m = ''
for i in range(len(a)):
for j in range(i,len(a)):
temp = a[i:j+1]
if b.find(temp)<0:
break
elif len(str_m)<len(temp):
str_m = temp
print(len(str_m))
except:
break ```

``` #include <bits/stdc++.h>
using namespace std;
int main()
{
string st;
while(cin>>st)
{
string str;
cin>>str;
int n=st.size();
int m=str.size();
vector<vector<int> > dp(n+1,vector<int>(m+1,0));
for(int i=1;i<n+1;i++)
{
for(int j=1;j<m+1;j++)
{
if(st[i-1]==str[j-1])
{
dp[i][j]= dp[i-1][j-1]+1;
}

}
}
int res=0;
for(int i=1;i<n+1;i++)
{
for(int j=1;j<m+1;j++)
{
if(dp[i][j]>res) res=dp[i][j];
}
}
cout<<res<<endl;
}
return 0;
} ```

```#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{     string a,b;     while(cin>>a>>b)     {         int n=a.size(),m=b.size();         int dp[n+1][m+1],Max=0;         memset(dp,0,sizeof(dp));         for(int i=1;i<=n;i++)             for(int j=1;j<=m;j++)             {                 if(a[i-1]==b[j-1])                 {                     dp[i][j] = dp[i-1][j-1] + 1;                     Max = max(Max, dp[i][j]);                         }             }         cout<<Max<<endl;     }     return 0;
}```

```import java.util.*;
public class Main{     String s1;     String s2;     public Main(){         Scanner scan=new Scanner(System.in);         s1=scan.next();         s2=scan.next();     }     public int getCommonStrLength(String ss1, String ss2 ){          String s3="",s4="";int k=0;         if(ss1.length()>ss2.length()){              s3=ss2;              s4=ss1;          }else{              s3=ss1;              s4=ss2;          }         for(int j=s3.length();j>0;j--){
int kk=0;             for(int i=0;i+j<=s3.length();i++){                 String s6=s3.substring(i, i+j);                 if(s4.contains(s6)){                     k=j;
kk=1;
break;                 }             }
if(kk==1){
break;
}
}         return k;     }     public static void main(String[]args){         Main nn=new Main();         int v=nn.getCommonStrLength(nn.s1, nn.s2);         System.out.println(v);     }
}

```

```#include <bits/stdc++.h>
using namespace std;
int main() {
string str1;
string str2;
while(cin>>str1>>str2){
int len1=str1.length(),len2=str2.length(),cnt,maxt=0,k;
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){k=0,cnt=0;
while(str1[i+k]==str2[j+k]&&i+k<=len1&&j+k<=len2){
cnt++;k++;
}if(maxt<cnt) maxt=cnt;
}
if(maxt==min(len1,len2)) break;
}
cout<<maxt<<'\n';
}
return 0;
} ```

// 经典动态规划，m为状态数组，m[i][j]表示a[i]，b[j]作为最长子串结尾时，最长子串的长度。

#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

int m[1000][1000];

int main() {
string a, b;
int max = -1;

cin >> a >> b;

for (int i = 0; i < a.length(); i++) {
for (int j = 0; j < b.length(); j++) {
if (a[i] == b[j]) {
if (i == 0 || j == 0) {
m[i][j] = 1;
}
else {
m[i][j] = 1 + m[i-1][j-1];
}
}
else {
m[i][j] = 0;
}

if (m[i][j] > max) {
max = m[i][j];
}
}
}

cout << max;

return 0;
}

154条回答 27321浏览

# 通过挑战的用户

• 2020-06-04 21:52:59
• 2020-06-04 21:43:27
• 2020-06-04 21:31:49
• 2020-06-04 21:20:38
• 2020-06-04 20:31:32

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题