公共子串计算

// 最长公共子串问题是面试常见题目之一
// 假设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;
		}

	}
}

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

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

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

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

使用较短字符串长度倒序遍历，取下标时在纸上推导很容易理解，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()

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

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

   
}

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

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

设置最大值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;
    }
}

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