查找两个字符串a,b中的最长公共子串

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <cctype>
#include <iomanip>
#include<cstdlib>
#include <functional>
#include <bitset>
using namespace std;

void FindCommonSubString()
{
	string str1, str2;
	while (cin >> str1 >> str2)
	{
		if (str1.size() > str2.size())
		{
			string temp = str2;
			str2 = str1;
			str1 = temp;
		}
		int sz1 = str1.size();
		int sz2 = str2.size();
		vector<vector<int>> dp(sz1, vector<int>(sz2, 0));
		for (int i = 0; i < sz1; ++i)
		{
			dp[i][0] = (str1[i] == str2[0] ? 1 : 0);
		}
		for (int i = 0; i < sz2; ++i)
		{
			dp[0][i] = (str2[i] == str1[0] ? 1 : 0);
		}
		for (int i = 1; i < sz1; ++i)
		{
			for (int j = 1; j < sz2; ++j)
			{
				if (str1[i] == str2[j])
				{
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
			}
		}
		int longest = 0;
		int start1 = 0;
		int start2 = 0;
		for (int i = 0; i < sz1; ++i)
		{
			for (int j = 0; j < sz2; ++j)
			{
				if (dp[i][j]>longest)
				{
					longest = dp[i][j];
					start1 = i - longest + 1;
					start2 = j - longest + 1;
				}
			}
		}
		cout << str1.substr(start1, longest) << endl;
	}
}

int main()
{
	FindCommonSubString();
	return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        System.out.println(longSubString(str1,str2));
    }
    public static String longSubString(String str1,String str2){
        String longStr = str1.length() > str2.length() ? str1 : str2;
        String shortStr = str1.length() < str2.length() ? str1 : str2;
        
        int shortLen = shortStr.length();
        int longLen = longStr.length();
        
        int maxLen = 0, start = 0;
        
        for(int i = 0; i < shortLen; i++){
            //双指针逐渐靠近
            for(int j = i, k = shortLen; k > j; k--){
                String subStr = shortStr.substring(j,k);
                if(longStr.contains(subStr) && maxLen < subStr.length()){
                    //此时找到一个公共子串
                    //把这个公共子串的长度设置为当前最大的长度
                    maxLen = subStr.length();
                    //把这个公共子串的起始位置设置为切割子串的起始位置
                    start = j;
                    //退出当前循环，进入下一个循环
                }
            }
        }
        return shortStr.substring(start,start+maxLen);
    }
}

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();
            String longStr = s1.length() > s2.length()? s1 : s2;
            String shortStr = s1.length() < s2.length()? s1 : s2;
            String maxSubStr = shortStr.substring(0,1);
            int maxSubLen = 1;
            for (int i = 1; i <= shortStr.length(); i++) { //每次截取长度为i的字符串  abcde 5
                for (int j = 0; j < shortStr.length()-i+1; j++) {
                    String str = shortStr.substring(j,j+i);//长度为i的字符串
                    if (longStr.contains(str) && str.length() > maxSubLen) {//该串是否在长串里
                        maxSubStr = str;
                        maxSubLen = str.length();
                    }
                }
            }
            System.out.println(maxSubStr);
        }
    }
}

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = "";
        while ((str = br.readLine()) != null) {
            String str1 = br.readLine();
            System.out.println(method(str, str1));
        }
        br.close();
    }
    private static String method(String s1, String s2) {
        String shortStr = s1.length() < s2.length() ? s1 : s2;
        String longStr = s1.length() < s2.length() ? s2 : s1;
        for (int i = 0; i < shortStr.length(); i++) {
            for (int j = 0, k = shortStr.length() - i; k <= shortStr.length(); j++, k++) {
                if (longStr.contains(shortStr.substring(j, k))) {
                    return shortStr.substring(j, k);
                }
            }
        }
        return null;
    }
}

while True:
    try:
        a,b,res=input(),input(),''
        short,long = (a,b) if len(a)<len(b) else (b,a)
        for i in range(len(short)):
            for j in range(len(short)):
                if short[i:j+1] in long and j+1 -i >len(res):
                    res = short[i:j+1]
        print(res)
    except:
        break

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String[] strings = new String[2];
            strings[0] = scanner.next();
            strings[1] = scanner.next();
            if (strings[0].length() > strings[1].length()){
                String temp = strings[0];
                strings[0] = strings[1];
                strings[1] = temp;
            }
            System.out.println(findLongestCommonSubStr(strings));
        }
    }
    public static String findLongestCommonSubStr(String[] strings){
        int max = strings[0].length();
        while (max >= 1){
            for (int i = 0; i <= strings[0].length()-max; i++){
                for (int j = 0; j <= strings[1].length()-max; j++){
                    if (strings[0].substring(i,i+max).equals(strings[1].substring(j,j+max))){
                        return strings[0].substring(i,i+max);
                    }
                }
            }
            max -= 1;
        }
        return null;
    }
}

while True:
    try:
        a, b = input(), input()
        if len(a)>len(b):
            a,b = b, a
        for i in range(len(a),0,-1):
            for j in range(len(a)-i+1):
                if a[j:j+i] in b:
                    print(a[j:j+i])
                    break
            else:
                continue
            break
    except:
        break

#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++])     len++;
                    if(max < len)
                    {
                        start = i;
                        max = len;
                    }
                }
            }
        }
        cout<<str1.substr(start,max)<<endl;
    }

    return 0;
}

public class Main{
    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        while (scanner.hasNext()) {
            char[] inputCharA = scanner.next().toCharArray();
            char[] inputCharB = scanner.next().toCharArray();
            String result;
            if (inputCharA.length > inputCharB.length) {
                result = find(inputCharB, inputCharA);
            } else {
                result = find(inputCharA, inputCharB);
            }
            System.out.println(result);
        }
    }

    public static String find(char[] inputCharA, char[] inputCharB) {
        int targetStartIndex = -1;
        int targetSubStrLength = -1;
        for (int i = 0; i < inputCharA.length; i++) {
            char charA = inputCharA[i];
            for (int j = 0; j < inputCharB.length; j++) {
                char charB = inputCharB[j];
                if (charA == charB) {
                    int counter = 1;
                    int tmpA = i + 1;
                    for (int h = j + 1; h < inputCharB.length; h++) {
                        if (tmpA < inputCharA.length) {
                            if (inputCharB[h] == inputCharA[tmpA]) {
                                counter++;
                                tmpA++;
                            } else {
                                break;
                            }
                        } else {
                            break;
                        }
                        if (counter > targetSubStrLength) {
                            targetSubStrLength = counter;
                            targetStartIndex = j;
                        }
                    }
                }

            }
        }
        StringBuilder stringBuffer = new StringBuilder();
        for (int i = 0; i < targetSubStrLength; i++) {
            stringBuffer.append(inputCharB[i + targetStartIndex]);
        }
        return stringBuffer.toString();
    }
}

def longest_public_str(str1,str2):
    if len(str1)>len(str2):
        long_str=str1
        short_str=str2
    else:
        long_str=str2
        short_str=str1
    
    # l 初始化
    l=[]
    for k in range(len(short_str)):
        if short_str[k] in long_str:
            l.append(short_str[k])
            break
    # l=['a']
    
    # 最长子串长度至少为2
    for i in range(len(short_str)):
        s=''
        s+=short_str[i]
        for j in range(i+1,len(short_str)):
            s+=short_str[j]
            if s in long_str and len(s)>len(l[0]):
                l.pop()
                l.append(s)
    return l[0]

while True:
    try:
        str1=input()
        str2=input()
        print(longest_public_str(str1,str2))
    except:
        break

c++

从最长长度往下遍历，取较短的那个字符串，去长的里面找，找到了直接退出输出即可

#include <iostream>
#include <string>
using namespace std;
//str1 < str2
string FindPublicStr(string str1, string str2)
{
    int len1 = str1.length(), len2 = str2.length();
    //从大到小遍历子串长度
    for(int l=len1; l>0; --l)
    {
        for(int i=0; i<len1-l+1; ++i)
        {
            int pos = str2.find(str1.substr(i, l));
            if(pos != -1)
                return str1.substr(i, l);
        }
    }
}
int main()
{
    string str1, str2;
    while(cin >> str1 >> str2)
    {
        if(str1.length() < str2.length())
            cout << FindPublicStr(str1, str2) << endl;
        else
            cout << FindPublicStr(str2, str1) << endl;
    }
}

while True:
    try:
        a = raw_input()
        b = raw_input()
        if len(a)>len(b):
            a,b = b,a
        ma = len(a)
        mb = len(b)
        ans = ""
        j = 1
        for i in range(ma):
            while j<=ma and a[i:j] in b:
                j += 1
            if (j-1-i)>len(ans):
                ans = a[i:j-1]
            if i == j:
                j += 1
        print ans
    except:
        raise

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            if(str2.length() < str1.length()) {
                String temp = str2;
                str2 = str1;
                str1 = temp;
            }
            int cnt = 0;//存储最长公共子串长度
            String need = "";//存储最长公共子串
            int first = Math.max(str1.length(),str2.length());//存储最长公共字符串出现位置
            for(int i=0; i<str1.length(); i++) {
                for(int j=i+1; j<str1.length(); j++) {
                    String substr = str1.substring(i, j+1);
                    if(str2.contains(substr)) {
                        if(substr.length() > cnt) {
                            cnt = substr.length();
                            need = substr;
                        }
                    }
                }
            }
            System.out.println(need);
        }
    }
}

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(str_m)
    except:
        break

#include <bits/stdc++.h>
using namespace std;
string findsame(string str1,string str2)
{
    int n=str1.size();
    int m=str2.size();
    vector<vector<int> > dp(n+1,vector<int>(m+1,0));
    dp[0][0]=0;
    int cnt=0,left;
    for(int i=1;i<n+1;i++)
    {
        for(int j=1;j<m+1;j++)
        {
            if(str1[i-1]==str2[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            if(dp[i][j]>cnt)
            {
                cnt = dp[i][j];
                left=i-cnt;
            }
        }

    }
    return str1.substr(left,cnt);
}
int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        if(str1.size()>str2.size())
        {
            swap(str1,str2);
        }
        cout<<findsame(str1,str2)<<endl;
    }
    return 0;
}