首页 > 试题广场 > 公共字串计算
[编程题]公共字串计算

题目标题:

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

详细描述:

接口说明

原型:

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 回复(9)
<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 回复(2)

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 回复(1)
#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 回复(1)
#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)
//思路:动态规划经典问题,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)
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)
//动态规划 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);
        }
	}
}



编辑于 2017-07-11 15:47:56 回复(4)
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));
        }       
    }
}

发表于 2016-10-14 21:33:02 回复(0)
#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;
}
编辑于 2016-04-23 00:37:26 回复(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;
}

发表于 2019-08-20 15:59:50 回复(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

发表于 2019-08-19 18:23:41 回复(0)
#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;
}

发表于 2019-08-12 22:43:01 回复(0)