首页 > 试题广场 >

公共子串计算

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

给定两个只包含小写字母的字符串,计算两个字符串的最大公共子串的长度。

注:子串的定义指一个字符串删掉其部分前缀和后缀(也可以不删)后形成的字符串。
数据范围:字符串长度:
进阶:时间复杂度:,空间复杂度:

输入描述:

输入两个只包含小写字母的字符串



输出描述:

输出一个整数,代表最大公共子串的长度

示例1

输入

asdfas
werasdfaswer

输出

6
#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 回复(9)
#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)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] A = sc.nextLine().toCharArray();
        char[] B = sc.nextLine().toCharArray();
        /**
         * dp[i][j] : A[0..i] 与 B[0..j]的最长公共子串长度
         *
         * dp[i][j] = dp[i-1][j-1] + 1 if A[i] == B[j]
         *          = 0
         *      A   a   s   d   f   a   s
         * B    0
         * w
         * e
         * r
         * a        1               1
         * s            2               2
         * d                3
         * f                    4
         * a                        5
         * s                            6
         * w
         * e
         * r
         */
        int[][] dp = new int[A.length + 1][B.length + 1];
        int max = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (A[i] == B[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (dp[i + 1][j + 1] > max)
                        max = dp[i + 1][j + 1];
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2022-07-03 01:20:42 回复(0)
// 最长公共子串问题是面试常见题目之一
// 假设str1长度N,str2长度M
// 因为最优解的难度所限,一般在面试场上回答出O(N*M)的解法已经是比较优秀了
// 因为得到O(N*M)的解法,就已经需要用到动态规划了
// 但其实这个问题的最优解是O(N+M),为了达到这个复杂度可是不容易
// 首先需要用到DC3算法得到后缀数组(sa)
// 进而用sa数组去生成height数组
// 而且在生成的时候,还有一个不回退的优化,都非常不容易理解
// 这就是后缀数组在面试算法中的地位 : 德高望重的噩梦
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine(), s2 = sc.nextLine();
        
        System.out.println(lcs2(s1,s2));
    }
    
    public static int lcs2(String s1, String s2) {
		if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
			return 0;
		}
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		int N = str1.length;
		int M = str2.length;
		int min = str1[0];
		int max = str1[0];
		for (int i = 1; i < N; i++) {
			min = Math.min(min, str1[i]);
			max = Math.max(max, str1[i]);
		}
		for (int i = 0; i < M; i++) {
			min = Math.min(min, str2[i]);
			max = Math.max(max, str2[i]);
		}
		int[] all = new int[N + M + 1];
		int index = 0;
		for (int i = 0; i < N; i++) {
			all[index++] = str1[i] - min + 2;
		}
		all[index++] = 1;
		for (int i = 0; i < M; i++) {
			all[index++] = str2[i] - min + 2;
		}
		DC3 dc3 = new DC3(all, max - min + 2);
		int n = all.length;
		int[] sa = dc3.sa;
		int[] height = dc3.height;
		int ans = 0;
		for (int i = 1; i < n; i++) {
			int Y = sa[i - 1];
			int X = sa[i];
			if (Math.min(X, Y) < N && Math.max(X, Y) > N) {
				ans = Math.max(ans, height[i]);
			}
		}
		return ans;
	}

	public static class DC3 {

		public int[] sa;

		public int[] rank;

		public int[] height;

		public DC3(int[] nums, int max) {
			sa = sa(nums, max);
			rank = rank();
			height = height(nums);
		}

		private int[] sa(int[] nums, int max) {
			int n = nums.length;
			int[] arr = new int[n + 3];
			for (int i = 0; i < n; i++) {
				arr[i] = nums[i];
			}
			return skew(arr, n, max);
		}

		private int[] skew(int[] nums, int n, int K) {
			int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
			int[] s12 = new int[n02 + 3], sa12 = new int[n02 + 3];
			for (int i = 0, j = 0; i < n + (n0 - n1); ++i) {
				if (0 != i % 3) {
					s12[j++] = i;
				}
			}
			radixPass(nums, s12, sa12, 2, n02, K);
			radixPass(nums, sa12, s12, 1, n02, K);
			radixPass(nums, s12, sa12, 0, n02, K);
			int name = 0, c0 = -1, c1 = -1, c2 = -1;
			for (int i = 0; i < n02; ++i) {
				if (c0 != nums[sa12[i]] || c1 != nums[sa12[i] + 1] || c2 != nums[sa12[i] + 2]) {
					name++;
					c0 = nums[sa12[i]];
					c1 = nums[sa12[i] + 1];
					c2 = nums[sa12[i] + 2];
				}
				if (1 == sa12[i] % 3) {
					s12[sa12[i] / 3] = name;
				} else {
					s12[sa12[i] / 3 + n0] = name;
				}
			}
			if (name < n02) {
				sa12 = skew(s12, n02, name);
				for (int i = 0; i < n02; i++) {
					s12[sa12[i]] = i + 1;
				}
			} else {
				for (int i = 0; i < n02; i++) {
					sa12[s12[i] - 1] = i;
				}
			}
			int[] s0 = new int[n0], sa0 = new int[n0];
			for (int i = 0, j = 0; i < n02; i++) {
				if (sa12[i] < n0) {
					s0[j++] = 3 * sa12[i];
				}
			}
			radixPass(nums, s0, sa0, 0, n0, K);
			int[] sa = new int[n];
			for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
				int i = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2;
				int j = sa0[p];
				if (sa12[t] < n0 ? leq(nums[i], s12[sa12[t] + n0], nums[j], s12[j / 3])
						: leq(nums[i], nums[i + 1], s12[sa12[t] - n0 + 1], nums[j], nums[j + 1], s12[j / 3 + n0])) {
					sa[k] = i;
					t++;
					if (t == n02) {
						for (k++; p < n0; p++, k++) {
							sa[k] = sa0[p];
						}
					}
				} else {
					sa[k] = j;
					p++;
					if (p == n0) {
						for (k++; t < n02; t++, k++) {
							sa[k] = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2;
						}
					}
				}
			}
			return sa;
		}

		private void radixPass(int[] nums, int[] input, int[] output, int offset, int n, int k) {
			int[] cnt = new int[k + 1];
			for (int i = 0; i < n; ++i) {
				cnt[nums[input[i] + offset]]++;
			}
			for (int i = 0, sum = 0; i < cnt.length; ++i) {
				int t = cnt[i];
				cnt[i] = sum;
				sum += t;
			}
			for (int i = 0; i < n; ++i) {
				output[cnt[nums[input[i] + offset]]++] = input[i];
			}
		}

		private boolean leq(int a1, int a2, int b1, int b2) {
			return a1 < b1 || (a1 == b1 && a2 <= b2);
		}

		private boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {
			return a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3));
		}

		private int[] rank() {
			int n = sa.length;
			int[] ans = new int[n];
			for (int i = 0; i < n; i++) {
				ans[sa[i]] = i;
			}
			return ans;
		}

		private int[] height(int[] s) {
			int n = s.length;
			int[] ans = new int[n];
			// 依次求h[i] , k = 0
			for (int i = 0, k = 0; i < n; ++i) {
				if (rank[i] != 0) {
					if (k > 0) {
						--k;
					}
					int j = sa[rank[i] - 1];
					while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
						++k;
					}
					// h[i] = k
					ans[rank[i]] = k;
				}
			}
			return ans;
		}

	}
}

发表于 2022-06-06 20:22:45 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int longestCommonSubstring(string text1, string text2) {
    int len1 = text1.size();
    int len2 = text2.size();
    int result = 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 (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = 0;
            }
            result = max(result, dp[i][j]);
        }
    }
    return result;
}
int main(){
    string text1;
    string text2;
    cin>>text1;
    cin>>text2;
    int result = longestCommonSubstring(text1, text2);
    cout<<result;
    return 0;
}

/*
1. 确定dp数组(dp table)以及下标的含义
    dp[i][j]:以 text[i - 1] text2[j - 1] 结尾的最⻓公共⼦串长度为 dp[i][j]
2. 确定递推公式
    主要就是两⼤情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同
    如果text1[i - 1] 与 text2[j - 1]相同,那么找到了⼀个公共元素,所以 dp[i][j] = dp[i - 1][j - 1] + 1;
    如果text1[i - 1] 与 text2[j - 1]不相同,dp[i][j] = 0;
3. dp数组如何初始化
    test1[0, i-1]和空串的最⻓公共⼦序列⾃然是0,所以dp[i][0] = 0;
    同理dp[0][j]也是0。
4. 确定遍历顺序
   从前向后,从上到下来遍历这个矩阵
*/
发表于 2022-04-05 23:02:34 回复(0)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String s1 = scan.nextLine();
            String s2 = scan.nextLine();
            System.out.println(Length(s1, s2));
        }
    }
    private static int Length(String s1, String s2) {
        String ss = s1.length() < s2.length() ? s1 : s2;
        String ls = s1.length() < s2.length() ? s2 : s1;

        for (int i = 0; i < ss.length(); i++) {
            for (int j = 0, k = ss.length() - i; k <= ss.length(); j++, k++) {
                String substring = ss.substring(j, k);
                if (ls.contains(ss.substring(j, k))) {
                    return substring.length();
                }
            }
        }
        return 0;
    }
}

发表于 2021-09-22 00:53:54 回复(0)
import java.util.Scanner;

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 res = 0;
            if(s1.length()<s2.length()){
                res = getMaxLength(s1, s2);
            }else{
                res = getMaxLength(s2, s1);
            }
            System.out.println(res);
        }
    }
    
    private static int getMaxLength(String s1, String s2){
        //特例
        if(s1==null || s1.length()==0) return 0;
        
        //暴力遍历寻找maxLen
        int maxLen=0;
        for(int i=0; i<s1.length(); i++){
            for(int j=i+1; j<=s1.length(); j++){
                if(s2.contains(s1.substring(i, j)) && j-i>maxLen){
                    maxLen = j-i;
                }
            }
        }
        return maxLen;
    }
}

发表于 2021-08-16 14:25:37 回复(0)
while True:
    try:
        list1=list(input())
        list2=list(input())
        list3=[]
        m=0
        n=0
        k=len(list1)
        w=len(list2)
        if k>w:
            list3=list2
            list2=list1
            list1=list3
            y=k
            k=w
            w=y
        for i in range(k):
            for j in range(w):
                if list1[i] == list2[j]:
                    n=1
                    o=min(k-i,w-j)
                    for r in range(i+1,i+o):
                        if list1[r]==list2[r+j-i]:
                            n+=1
                            m=n if n>m else m
                        else:
                            break
        print(m)
    except:
        break
发表于 2021-03-16 11:11:39 回复(0)
a = input()
b = input()
if len(a) > len(b):
    a, b = b, a
max_len = 0
i = 0
while i + max_len < len(a):
    while a[i:i + max_len + 1] in b and i + max_len + 1 < len(a):
        max_len += 1
    i += 1
print(max_len)

发表于 2021-02-24 21:20:33 回复(0)
O(n)复杂度,python
while True:
    try:
        a = input()
        b = input()
        if len(a) > len(b):
            a,b = b,a
        max_length = 0
        i = 0
        while i + max_length < len(a):
            while a[i:i + max_length + 1] in b:
                max_length += 1
            i += 1
        print(max_length)
    except:
        break


发表于 2021-02-21 17:52:29 回复(0)
这个代码挺好理解,也可以通过。
但是自测结果跟预期输出不一样,为什么可以通过呢?
有没有大神解释一下?
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        //保证str1是比较短的一个串
        if(str1.size()>str2.size())    swap(str1,str2);

        int start = 0;//最长公共字符串的开始位置
        int max = 0;//最长公共字串的长度
        //用短串中的字符去挨个匹配长串中的字符,如果匹配的上,则继续短串和长串往后比,同时len++
        //直到短串中的字符和长串中的字符不一样时,则,记录下最大长度
        for(int i = 0;i<str1.size();i++)
        {
            for(int j = 0;j<str2.size();j++)
            {
                if(str1[i] == str2[j])
                {
                    int tmpi = i;
                    int tmpj = j;
                    int len = 0;
                    while(str1[tmpi++] == str2[tmpj++])
                    {
                        if(tmpi < str1.size() && tmpj < str2.size())
                            len++;
                    }
                    if(max < len)
                    {
                        start = i;
                        max = len;
                    }
                }
            }
        }
        cout<<max<<endl;
    }

    return 0;
}


发表于 2021-01-30 09:32:42 回复(0)
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		while (in.hasNext()) {
			String min = in.next();
			String max = in.next();
			if (min.length() > max.length()) {
                String tmp=max;
				max = min;
				min = tmp;
			} 
			System.out.println(common(min, max));
		}
	}

	private static int common(String min, String max) {
		for (int i = min.length(); i > 0; i--) {
			// 截取长度
			for (int j = 0; j <= min.length() - i; j++) {
				// index
				if (max.contains(min.substring(j, j+i)))
					return i;
			}
		}
		return 0;
	}
}

编辑于 2020-11-16 17:19:58 回复(0)

使用较短字符串长度倒序遍历,取下标时在纸上推导很容易理解,exit()退出程序


a = input().lower()
b = input().lower()
maxlen = min(len(a),len(b))
for i in range(maxlen,0,-1):
    for p in range(0,len(a)-i+1):
        for q in range(0,len(b)-i+1):
            if a[p:p+i] == b[q:q+i]:
                print(i)
                exit()



发表于 2020-10-13 16:45:37 回复(0)
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string st;
    string ss;
    while(cin >> st >> ss)
    {
        int max = 1;
        for(int i=0;i<st.size();i++)
        {
            if(st[i]>='A' && st[i]<='Z')
                st[i] = st[i] + 32;
        }
        
        for(int i=0;i<ss.size();i++)
        {
            if(ss[i]>='A' && ss[i]<='Z')
                ss[i] = ss[i] + 32;
        }
        
        for(int j=0;j<st.size();j++)
        {
            for(int k=j+1;k<st.size();k++)
            {
                string temp;
                temp = st.substr(j,k-j+1);
                if(int(ss.find(temp))>=0)     
                {
                    if(temp.size()>max)
                        max=temp.size();
                }
                else
                    break;
            }
        }
        cout << max << endl;
    }
    return 0;
}

发表于 2020-09-01 14:14:33 回复(0)
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
            
         String str1 = scanner.nextLine();
         String str2 = scanner.nextLine();
            
         System.out.println(fun(str1,str2));
        
    }
    public static int fun(String s1,String s2){
        int max = 0;
        
        byte[][] result = new byte[s1.length()][s2.length()];
        for(int i=0;i<s1.length();i++){
            for(int j=0;j<s2.length();j++){
                
                if(s1.charAt(i)==s2.charAt(j)){
                    if(i==0 || j==0){
                        result[i][j]++;
                    }else{
                        result[i][j] = ++result[i-1][j-1];
                        max = Math.max(max,result[i][j]);
                    }
                }
            }
        }
        
        return max;
    }

   
}






发表于 2020-08-01 22:07:21 回复(0)
暴力枚举方法做的,感觉不是很好,应该有更好的,看评论区还有动态规划的,可以学习一下
while True:
    try:
        a, b, maxl = input().upper(), input().upper(), 0
        if len(a) > len(b): a, b = b, a
        for i in range(len(a)):
            for j in range(len(a), -1, -1):
                if a[i:j] in b:
                    maxl = max(maxl, len(a[i:j]))
        print(maxl)
    except:
        break


发表于 2020-07-20 17:14:00 回复(0)
while True:
    try:
        str1 = input().upper()
        str2 = input().upper()
        strL = str1 if len(str1)>=len(str2) else str2
        strS = str1 if len(str1)<len(str2) else str2
        for i in range(len(strS)):
            for j in range(i):
                if(strS[j:len(strS)-i+j] in strL):
                    print(len(strS[j:len(strS)-i+j]))
                    exit()
    except:
        break
发表于 2020-07-12 23:03:23 回复(2)
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        //保证str1是比较短的一个串
        if(str1.size()>str2.size())    swap(str1,str2);

        int start = 0;//最长公共字符串的开始位置
        int max = 0;//最长公共字串的长度
        //用短串中的字符去挨个匹配长串中的字符,如果匹配的上,则继续短串和长串往后比,同时len++
        //直到短串中的字符和长串中的字符不一样时,则,记录下最大长度
        for(int i = 0;i<str1.size();i++)
        {
            for(int j = 0;j<str2.size();j++)
            {
                if(str1[i] == str2[j])
                {
                    int tmpi = i;
                    int tmpj = j;
                    int len = 0;
                    while(str1[tmpi++] == str2[tmpj++])
                    {
                        if(tmpi < str1.size() && tmpj < str2.size())
                            len++;
                    }
                    if(max < len)
                    {
                        start = i;
                        max = len;
                    }
                }
            }
        }
        cout<<max<<endl;
    }

    return 0;
}

发表于 2020-07-11 10:34:49 回复(2)
这题本身难度不高,本人利用两重循环通过遍历的方式实现,外层循环是公共字符串可能的长度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)