[编程题]公共字串计算

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];
}
} ```

<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>

# 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;
}```

```#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();
}
}```

```//思路:动态规划经典问题，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;
}```

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;
}

```//动态规划 if(a[i]==b[j])c[i][j]=c[i-1][j-1]+1;else c[i][j]=0; longSubString=max(c[i][j])
import java.util.Scanner;
public class Main {
public static void commenSub(String s1,String s2){
s1=" "+s1;//相当于初始化a[0]=0;a[1]~a[m-1]=s1;
s2=" "+s2;
char a[]=s1.toCharArray();
char b[]=s2.toCharArray();
int m=a.length;
int n=b.length;
int c[][]=new int[m][n];
int max=0;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(a[i]==b[j]){//相等
c[i][j]=c[i-1][j-1]+1;
}else{//不等
c[i][j]=0;
}
if(max<c[i][j]){max=c[i][j];}//记录最长字串
}
}
System.out.println(max);
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String s1=sc.next();
String s2=sc.next();
commenSub(s1,s2);
}
}
}

```

```import java.util.*;

public class Main{

public static int getCommonStrLength(String first, String second){

int m = first.length();
int n = second.length();
int count = 0;
int len = 0;
String s,t,temp;

if(m > n){
s =  first.toLowerCase();
t =  second.toLowerCase();  // 保障s是长的那个字符串
}
else{
s =  second.toLowerCase();
t =  first.toLowerCase();  // 保障s是长的那个字符串
}

m = s.length();
n = t.length();
for(int i = 0; i < n; i++){
for(int j = i + 1; j <= n; j++){
temp = t.substring(i, j);
if(s.indexOf(temp) != -1)
len = temp.length();
count = count < len ? len: count;
}
}
return count;
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String first = in.next();
String second = in.next();
System.out.println(getCommonStrLength(first, second));
}
}
}```

#include <stdio.h>
#include <string.h>
#define max 1000
char str1[max];
char str2[max];
int len1=0,len2=0,maxlen=0;
int getCommonStrLength(const char *str1,const char *str2,int cmpLen)
{
int retMax=0;
int co=0;
for(int i=0;i<cmpLen;i++){
if(*(str1+i) == *(str2+i)){
co++;
}
else{
retMax = retMax<co?co:retMax;
co=0;
}
}
retMax = retMax<co?co:retMax;
return retMax;
}
int main()
{
scanf("%s",str1)>0;
scanf("%s",str2)>0;
len1 = strlen(str1);
len2 = strlen(str2);
//printf("%s\n",str2);
/*
1. str1在上，str2在下，初始将str1最后一个字符与str2第一个字符对齐；
2. 查找对齐部分字符串最大公共字串长度。
3. 将str1右移，执行“2”，直到str1第一个字符与str2最后一个字符对齐。
4. 取每次执行“2”得到最大值。
*/
for(int i= 1;i<len1+len2;i++){
const char *ss1 = NULL; //此次比较从 str1 中的地址ss1开始。
const char *ss2 = NULL;
int cmpLen1=0;
int cmpLen2=0;
if(i>=len1){
ss1 = str1;
ss2 = str2+(i-len1);
cmpLen1 = len1;
cmpLen2 = len2-(i-len1);
}
else {
ss1 = str1+(len1-i);
ss2 = str2;
cmpLen1 = i;
cmpLen2 = len2;
}
int cmpLen = cmpLen1>cmpLen2?cmpLen2:cmpLen1; //该次比较实际长度
if(cmpLen>=maxlen)
{
int testRet = getCommonStrLength(ss1, ss2, cmpLen);
maxlen= maxlen<testRet?testRet:maxlen;
}
}
printf("%d\n",maxlen);
return 0;
}

```#include<stdio.h>
#include<string.h>

int main()
{
char str1[512],str2[512];
while(scanf("%s %s",str1,str2)!=EOF){
int len1,len2,i,ii,j,jj,max = 0,sublen = 0;
len1 =strlen(str1);
len2=strlen(str2);

for(i=0,j=0;i<len1;){
sublen = 0;
ii = i; jj = j;
while((ii<len1) && (jj<len2) && (str1[ii]==str2[jj])){
sublen++;
ii++;
jj++;
}
j++;
if(sublen>max)
max = sublen;
if(j>=len2){
i++;
j=0;
}

}
printf("%d\n", max);
}
return 0;
}```

```import re
while True:
try:
s = input() + '\n' + input()
L = [re.search(r'(.+)(?=.*\n.*\1)', s[i:]) for i in range(len(s))]
L = [i.group() for i in L if i]
print(len(max(L, key = len)))
except: break```

```#include<iostream>
#include<string>
#include<vector>
using namespace std;
void FindCom(string &s1,string &s2)
{
int len1=s1.size();
int len2=s2.size();
vector<vector<int>>dp(len1,vector<int>(len2,0));

int res=0;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(s1[i]==s2[j])
{
if(i==0||j==0)
{
dp[i][j]=1;//第1行或者1列 相等情况
}
else
{
dp[i][j]=dp[i-1][j-1]+1;//对角线
}
}
res=max(res,dp[i][j]);
}
}
cout<<res;
return ;
}
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
FindCom(s1,s2);
}
return 0;
}```

118条回答 20666浏览

# 通过挑战的用户

• 2019-08-23 22:18:09
• 2019-08-23 21:17:19
• 2019-08-23 20:28:57
• 2019-08-23 16:52:50
• 2019-08-23 15:50:35

# 相关试题

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

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