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

题目标题:

计算两个字符串的最大公共字串的长度,字符不区分大小写

详细描述:

接口说明

原型:

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

输入参数:

     char * pFirstStr //第一个字符串

     char * pSecondStr//第二个字符串

 


输入描述:

输入两个字符串



输出描述:

输出一个整数

示例1

输入

asdfas
werasdfaswer

输出

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

举个栗子:
str1="123ABCD456"  str2 = "ABE12345D"
最长公共子串是:123
最长公共子序列是:12345

这两个都可以用动态规划,只是状态转移方程有点区别

最长公共子序列是:
dp[i][j] -- 表示子串str1[0...i]和子串str[0...j]的最长公共子序列
当str1[i] == str2[j]时,dp[i][j] = dp[i-1][j-1] + 1;
否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
最优解为dp[len1-1][len2-1];

最长公共子串是: dp[i][j] -- 表示以str1[i]和str2[j]为结尾的最长公共子串 当str1[i] == str2[j]时,dp[i][j] = dp[i-1][j-1] + 1; 否则,dp[i][j] = 0;
最优解为max(dp[i][j]),其中0<=i<len1, 0<=j<len2;

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



编辑于 2016-07-10 09:33:35 回复(10)

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
发表于 2017-10-06 10:14:20 回复(3)
#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;
}

发表于 2017-04-15 10:08:15 回复(4)
<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>
编辑于 2017-08-16 16:06:05 回复(4)
#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;
}

发表于 2016-05-17 14:54:58 回复(8)
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();
    }
}
发表于 2018-04-06 18:10:42 回复(0)
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;
}


发表于 2019-11-29 18:25:39 回复(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;
}

发表于 2017-02-05 09:59:42 回复(0)
这题本身难度不高,本人利用两重循环通过遍历的方式实现,外层循环是公共字符串可能的长度i,内层循环是两个字符串中短的字符串每个字母对应的索引游标j(遍历短的字符串去对应找长的字符串中是否包含该字符串)。但是在代码中需要注意几个细节,可以提高代码的执行效率。
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


编辑于 2020-03-13 09:25:41 回复(0)
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

发表于 2020-03-03 22:31:27 回复(0)
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);
            }
        }
    }
}

发表于 2020-02-19 01:07:53 回复(0)
把两个字符串都转成大写再进行比较。
对小串进行循环,用contain就能比较包含了。
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--;
            }
        }
    }
}


发表于 2020-02-02 19:08:00 回复(0)

设置最大值maxlen

如果j-i > maxlen 则更新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;
    }
}
发表于 2019-11-28 19:16:41 回复(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 

发表于 2019-03-16 12:08:43 回复(1)
 #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;
} 

发表于 2018-08-08 21:37:30 回复(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;
}
发表于 2018-06-01 01:12:56 回复(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);     }
}

发表于 2018-04-07 00:01:47 回复(0)
#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;
} 

发表于 2017-11-24 22:28:53 回复(0)
求两个长度mn的字符串的公共子串的长度,可以看成从长度为1开始每次进行遍历判断分别长度为ij的两个子串的公共子串的长度,每次进行加1

编辑于 2017-09-18 13:05:57 回复(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;
}
发表于 2017-06-23 16:01:24 回复(0)