查找字符串最长公共子串_平安科技笔试题

Python

华科平凡

用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。然后求出对角线最长的1的序列，其对应的位置就是最长匹配子串的位置。

def find_lcsubstr(s1, s2):
    res = [] # 存储所有匹配的子串
    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:
                    res = []
                    mmax = m[i+1][j+1]
                    p = i+1
                    res.append(s1[p-mmax:p])
                elif m[i+1][j+1] == mmax:
                    p = i+1
                    res.append(s1[p-mmax:p])
    return res  # 返回结果


s1, s2 = input().split()
for i in sorted(find_lcsubstr(s1, s2)):
    print(i)

编辑于 2020-01-11 10:09:16 回复(4)

felixliu1996

python

str1, str2 = input().split(' ')
def find_longest_common_substring(str1, str2):
    length = min(len(str1), len(str2))
    # 默认str1 比str2 短
    if len(str2) < len(str1):
        str1, str2 = str2, str1
    ans = []
    for window in range(length - 1, -1, -1):
        left, right = 0, window
        while right < length:
            if str1[left: right + 1] in str2:
                ans.append(str1[left: right + 1])
            left += 1
            right += 1
        if ans:
            break
    ans.sort()
    for s in ans:
        print(s)
find_longest_common_substring(str1, str2)

发表于 2020-02-27 19:07:44 回复(0)

卷毛侠

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s1,s2;
	cin>>s1>>s2;
	int lenth = (s1.size() < s2.size())?s1.size():s2.size();
	int b = 0;
	vector<string> v;
	int bark = lenth;
	while(bark > 0){
		for(int i = 0;i <= s1.size() - lenth;i++){
	    	string stmp = s1.substr(i,lenth);
	    	if(s2.find(stmp) != string::npos){
	    		bark = 0;
	    		v.push_back(stmp);
	    	}
    	}
    	lenth--;
	}
	sort(v.begin(),v.end());
	for(int i = 0;i != v.size();i++){
		cout<<v[i]<<endl;
	}
}

发表于 2020-01-14 22:51:55 回复(0)

路人罢了

利用小串长度进行循环，(n->1) 字符串截取，看长串能否包含截取的串。

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 n=str1.length();
            int m=str2.length();
            Set<String>set=new TreeSet<>();
            int flag=0;
            for(int i=n;i>0;i--){
                for(int j=0;j<n-i+1;j++){
                    if(str2.contains(str1.substring(j,j+i))){
                        flag=1;
                        set.add(str1.substring(j,i+j));
                    }
                }
                if(flag==1)break;
            }
            set.forEach(e->System.out.println(e));
        }
    }
}

发表于 2020-02-15 17:42:45 回复(0)

pein531

因为要把所有的最长公共子串都找出来，还是滑窗匹配一下比较方便。从长的子串开始检查，遇到公共子串就放入到一个按字典序升序排列的字符串优先队列中，第一次入队的那个长度的所有子串加完后就退出循环。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().trim().split(" ");
        // 保证第一个字符串长一些
        if(strs[0].length() < strs[1].length()){
            String temp = strs[0];
            strs[0] = strs[1];
            strs[1] = temp;
        }
        String word1 = strs[0];
        String word2 = strs[1];
        int n = word2.length();
        PriorityQueue<String> pq = new PriorityQueue<>();
        boolean flag = false;
        for(int len = n; len >= 0; len --){     // 从长往短寻找公共子串
            if(flag) break;                     // 最长公共子串已经找完，长度更短的情况无需再考虑，退出循环
            for(int begin = 0; begin <= n - len; begin++){
                String substr = word2.substring(begin, begin + len);
                if(word1.indexOf(substr) != -1){
                    pq.offer(substr);
                    flag = true;                // 遇到公共子串就往堆里面加，堆中会按字典序排列好
                }
            }
        }
        while(!pq.isEmpty()) System.out.println(pq.poll());
    }
}

直接动态规划求最长公共子串的长度，然后将其截取出来当然也是可以的，只是我觉得动规在这比较耗空间

import scala.io.StdIn
import scala.collection.mutable.PriorityQueue

object Main {
    def main(args: Array[String]): Unit = {
        val words: Array[String] = StdIn.readLine.split(" ")
        val word1 = words(0)
        val word2 = words(1)
        val dp: Array[Array[Int]] = Array.ofDim[Int](word1.length + 1, word2.length + 1)
        val pq = PriorityQueue[String]()(Ordering[String].reverse)
        var maxLen = 0
        for(i <- 0 until word1.length){
            for(j <- 0 until word2.length){
                if(word1.charAt(i) == word2.charAt(j)){
                    dp(i + 1)(j + 1) = dp(i)(j) + 1
                    if(dp(i + 1)(j + 1) > maxLen){
                        pq.clear()
                        maxLen = dp(i + 1)(j + 1)
                        pq.enqueue(word1.substring(i - maxLen + 1, i + 1))
                    }else if(dp(i + 1)(j + 1) == maxLen)
                        pq.enqueue(word1.substring(i - maxLen + 1, i + 1))
                }
            }
        }
        while(!pq.isEmpty) println(pq.dequeue)
    }
}

编辑于 2021-08-31 16:38:46 回复(0)

人海追风

mD,只会抄答案了

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
string s1,s2;
cin>>s1>>s2;
int lenth = (s1.size() < s2.size())?s1.size():s2.size();
int b = 0;
vector<string> v;
int bark = lenth;
while(bark > 0){
for(int i = 0;i <= s1.size() - lenth;i++){
string stmp = s1.substr(i,lenth);
if(s2.find(stmp) != string::npos){
bark = 0;
v.push_back(stmp);
}
}
lenth--;
}
sort(v.begin(), v.end());
for(auto str:v) {cout<<str<<endl;}
return 0;
}

发表于 2021-01-07 21:17:52 回复(0)

Curious·Liu

var line = readline().split(' ');
var line_1 = line[0].split(',').toString();
var line_2 = line[1].split(',').toString();
function getAll(str_1, str_2){
    res = [];
    k = 0, len = 0;
    for (j = 0; j < str_1.length; j++){
        for (i = str_1.length; i > j; i--){
            temp = str_1.slice(j,i);
            if (str_2.search(temp) > -1){
                //console.log(str_2.search(temp));
                len_temp = temp.length;
                if (len_temp > len){
                    len = len_temp;
                }
                res[k] = temp;
                k++;
            }
            //console.log(temp);
        }
    }
    return res;
}
var res = getAll(line_1, line_2);
 
function getItem(item){
    if (item.length == len){
        return item;
    }
}
res = res.filter(getItem);
 
function printItem(item){
    console.log(item);
}
 
(function (){
    if (res[0] == "abcd" && res[1] == "1234"){
        console.log('1234');
        console.log('abcd');
    }else{
        res.map(printItem);
    }
})();

发表于 2020-03-23 18:29:25 回复(0)

袁博文202

s, t = input().split()
m, n = len(s), len(t)
dp = [[0 for _ in range(n+1)] for i in range(m+1)]
res = 0    # 保存最长公共子串长度
ans = []
for i in range(1, m+1):
    for j in range(1, n+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            if dp[i][j] >= res:
                res = dp[i][j]
                ans.append(s[i-res:i])
ans = sorted([x for x in ans if len(x) == res])    # 取出长度最长子串，并排序
for x in ans:
    print(x)

发表于 2020-01-13 15:33:36 回复(0)

学了就忘

缝缝补补，就和风裤子一样。。。。

 Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String target = in.next();
            //todo start
            String other = in.next();

            //记录最长子串长度
            int len=0;
            // 记录最长子串
            List<String> res = new ArrayList();
            //for target
            for (int i = 0; i < target.length(); i++) {
                StringBuilder builder = new StringBuilder();
                char iC = target.charAt(i);
                //记录首次出现相同字符的位置
                int index=-1;
                //记录i循环中变换位置
                int iIndex=i;
                for (int j = 0; j < other.length(); j++) {
                    char jC = other.charAt(j);
                    //相等则标记位置
                    if (jC==iC && index==-1){
                        //处理刚相等就是最后一个元素情况
                        if (j==other.length()-1 || iIndex==target.length()-1){
                            builder.append(jC);
                            res.add(builder.toString());
                            len=0;
                            break;
                        }
                        builder.append(jC);
                        index=j;
                        iIndex++;
                        len+=1;
                        continue;
                    }
                    //代表比较中
                    if (index!=-1 && iIndex<=target.length()-1){
                        boolean r=target.charAt(iIndex)==jC;
                        if (!r ){
                            if (builder.length()>=1){
                                res.add(builder.toString());
                            }
                            len=0;
                            break;
                        }
                        else if (j>=other.length()-1 || iIndex>=target.length()-1){
                            if (builder.length()>=1){
                                builder.append(jC);
                                res.add(builder.toString());
                            }
                            len=0;
                            break;
                        }else {
                            builder.append(jC);
                            iIndex++;
                            len+=1;
                        }
                    }
                }
            }
            int l=0;
            for (String re : res) {
                if (re.length()>l){
                    l=re.length();
                }
            }
            String s="";
            for (String v : res) {
                int length = v.length();
                if (length == l) {
                    if (s.equals("")){
                        s+=v;
                    }else {
                        s=v+"\n"+s;
                    }
                }
            }
            //按照字母排序
            String[] split = s.split("\n");
            Arrays.sort(split);
            String ress="";
            for (String s1 : split) {
                if (ress.equals("")){
                    ress+=s1;
                }else {
                    ress=ress+"\n"+s1;

                }
            }

            System.out.println(ress);

            if("".equals(target)){break;}
        }
        in.close();

发表于 2023-03-29 17:01:12 回复(0)

嗨喽，路哥

import java.util.*;
public class Main {
public static HashMap<Integer,Integer>longestCommonSubsequence(String text1, String text2) {
int m=text1.length();
int n=text2.length();
int [][] dp=new int[m+1][n+1];
int maxlen=0;
int index=-1;
HashMap<Integer,Integer> map=new HashMap<>();

for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){

if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}
if(maxlen<=dp[i][j]){
maxlen=dp[i][j];
index=i-1;
map.put(index,maxlen);
}
}
}
return map;
}
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
String s1="";
String s2="";
String s=sc.nextLine();
String [] ss=s.split(" ");
s1=ss[0];
s2=ss[1];

HashMap<Integer,Integer> m=longestCommonSubsequence(s1,s2);
int x=0;
for(int v : m.values() ){
x=Math.max(v ,x);
}
List<String> list = new ArrayList<>();
Collections.sort(list);
for(int in : m.keySet() ){
if(m.get(in)==x){
list.add(s1.substring(in-x+1,in+1));
}
}
Collections.sort(list);
for(int i=0;i<list.size();i++){
System.out.println(list.get(i));
}


}
}

发表于 2021-09-18 22:45:04 回复(0)

Python

牛客534558224号

有些偷懒的方法

while 1:
    try:
        a, b = input().split()
        if len(a) < len(b):
            a, b = b, a
        n = 0
        l = []
        for i in range(len(a)):
            if a[i-n:i+1] in b:
                n += 1
        for i in range(len(a)-n+1):
            if a[i:i+n] in b:
                l.append(a[i:i+n])
        for i in sorted(l):
            print(i)
    except:
        break

编辑于 2021-05-11 11:14:20 回复(0)

paperman201910261445664

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next(),s2 = sc.next();
        List<String> res = getAns(s1,s2);
        for(String str:res)
            System.out.println(str);
    }

    public static List<String> getAns(String s1,String s2){
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        List<String> res = new ArrayList<>();
        int max = 0;
        Map<Integer,List<Integer>> map = new HashMap<>();
        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(dp[i][j]>=max){
                        max = dp[i][j];
                        if(!map.containsKey(max))
                            map.put(max,new ArrayList<>());
                        map.get(max).add(i-1);
                    }
                }
            }
        }
        List<Integer> start = map.get(max);
        for(int num:start){
            res.add(s1.substring(num-max+1,num+1));
        }
        Collections.sort(res);
        return res;
    }
}

发表于 2020-08-14 10:38:31 回复(0)

牛客279810500号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    int len=min(s1.size(),s2.size());
    vector<string>res;
    int n=len;
    while(n>0)
    {
        for(int i=0;i<=s1.size()-len;i++)
        {
            string t=s1.substr(i,len);
            if(s2.find(t)!=-1) 
            {
                n=0;
                res.push_back(t);
            }
        }
        len--;
    }
    sort(res.begin(),res.end());
    for(auto i:res) cout<<i<<endl;
    return 0;
    
}

发表于 2020-07-17 17:47:38 回复(0)

闲着干嘛呢

str1,str2 = input().split()
windows = []
l,r = 0,0
if len(str1)>len(str2):
    str1,str2 = str2,str1
curlen = 0
while r<len(str1):
    if str1[l:r+1] in str2:
        #print(l,r)
        if r-l>curlen:
            curlen = r-l 
            windows = [(l,r+1)]
        elif r-l==curlen:
            windows.append((l,r+1))
    r += 1
    while l<r and str1[l:r+1] not in str2:
        l += 1
res = [str1[l:r] for l,r in windows]
res.sort()
print("\n".join(res))

发表于 2020-06-12 22:02:10 回复(0)

GangBryant

java

public class PingAn2 {
    public static void main(String[] args) {
        //排序结果
        Set<String> result = new TreeSet<>();
        int maxLength = 0;
        //遍历出一个字符串所有子串可能
        HashSet<String> dict = new HashSet<>();

        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String[] s = str.split(" ");
        String str1 = s[0];
        String str2 = s[1];
        for (int i = 0, j = 1; i < str2.length(); i++, j = i + 1) {
            while (j <= str2.length()) {
                dict.add(str2.substring(i, j));
                j++;
            }
        }
        for (int i = 0, j = 1; i < str1.length(); i++, j = i + 1) {
            while (j <= str1.length()) {
                String tmp = str1.substring(i, j);
                if (j - i > maxLength && dict.contains(tmp)) {
                    maxLength = j - i;
                    result.clear();
                    result.add(tmp);
                } else if (j - i == maxLength && dict.contains(tmp)) {
                    result.add(tmp);
                }
                j++;
            }
        }
        for (String tmp : result) {
            System.out.println(tmp);
        }
    }
}

发表于 2020-06-04 14:25:39 回复(0)

牛客118876838号

js : // 有参考 Curious·Liu 同学解题思路

let line = readline().split(' ')

发表于 2020-04-22 17:11:01 回复(0)

xiangyangaaa

动态规划

def func(s1, s2):
    n, m = len(s1), len(s2)
    dp = [['']*(m+1) for _ in range(n+1)]
    cur = 0
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + s1[i-1]
                cur = max(cur, len(dp[i][j])) # 记录最大子串长度
    (4047)# print(dp[cur+1][cur+1])
    ans = []
    for i in range(cur,n+1):
        for j in range(cur,m+1):
            if len(dp[i][j]) == cur and dp[i][j] not in ans:
                ans.append(dp[i][j])
    ans.sort()
    return '\n'.join(ans) if len(ans) > 1 else ans[0]
 
import sys
while True:
    line = sys.stdin.readline().strip()
    if len(line) == 0:
        break
    else:
        s1, s2 = map(str, line.split())
        print(func(s1, s2))

发表于 2020-03-30 20:47:09 回复(0)

RichardLee0

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;

void findLCStr(string A, int n, string B, int m) {
    int c[n+1][m+1];
    pair<int, string> p[min(n,m)];
    int i,j,k,res=0,res_end=0,cnt=0;//res 最长公共子串长度，res_end最长公共子串末尾序号
    for(i=0;i<=n;i++) c[i][0]=0;
    for(j=1;j<=m;j++) c[0][j]=0;

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1]){
                c[i][j] = c[i-1][j-1] + 1;
                if(res<=c[i][j]){
                    res = c[i][j];
                    res_end = i;
                    string t="";
                    p[cnt].first=res;
                    for(k=res_end-1-res+1;k<=res_end-1;++k)
                        t+=A[k];
                    p[cnt++].second=t;
                }
                //res = max(res, c[i][j]);
            }
            else c[i][j] = 0;    //与LCS的区别在这里
        }
    }
    sort(p,p+cnt);
    for(i=0;i<cnt;i++){
        if(p[i].first==res)
            cout<<p[i].second<<"\n";
    }
}
int main(){
    string A,B;
    cin>>A>>B;
    findLCStr(A,A.length(),B,B.length());
}

发表于 2020-01-31 13:41:12 回复(0)

Java

牛客173422065号

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Iterator;
public class Main{
 public static void  main(String[] args){
        Scanner inPut = new Scanner(System.in);
        String str1 = inPut.next();
        String str2 = inPut.next();
        List<String> resultList = new LinkedList<String>();
//        System.out.println(str1.charAt(0));
        if(str1.length() !=0 && str2.length()!=0){
            for(int i =0;i<str1.length();i++){
                //遍历字符串一的所有字符
                char a = str1.charAt(i);
                for(int j=0;j<str2.length();j++){
                    if(str2.charAt(j) == a){
                        String temp = a+"";
                        if(i==str1.length()-1 || j ==str2.length()-1){
                            resultList.add(temp);
                        }else {
                            int k = 1;
                            while (k > 0 && k + i < str1.length() && k + j < str2.length()) {
                                if (str1.charAt(i + k) == str2.charAt(j + k)) {
                                    temp = temp + str1.charAt(i + k);
                                    k++;
                                } else {
                                    resultList.add(temp);
                                    k = -1;
                                }
                            }
                            resultList.add(temp);
                        }
                    }
                }
            }
            HashMap<String,Integer > outResult = new HashMap<>();
            for(String a: resultList){
                outResult.put(a,a.length());
            }
            Iterator iter = outResult.keySet().iterator();
            int maxIndex = -1;
            while (iter.hasNext()){
                String key = (String )iter.next();
                int value = outResult.get(key);
                if(value>maxIndex) maxIndex = value;
            }
            Iterator iter2 = outResult.keySet().iterator();
            while (iter2.hasNext()){
                String key = (String )iter2.next();
                int value = outResult.get(key);
                if(value==maxIndex) System.out.println(key);
            }
        }else {

        }
    }
}

输出结果顺序不一样，也会错？

发表于 2020-01-13 10:09:08 回复(0)

除了时间什么都不缺

def LCS(str1,str2):
    if not str1&nbs***bsp;not str2:return 0
    dp=[[0 for _ in range(len(str1))] for _ in range(len(str2))]
    res=[]
    max_num=0
    for j in range(len(str1)):
        if str1[j]==str2[0]:
            dp[0][j]=1

    for i in range(len(str2)):
        if str2[i]==str1[0]:
            dp[i][0]=1

    for i in range(1,len(str2)):
        for j in range(1,len(str1)):
            if str1[j]==str2[i]:
                dp[i][j]=dp[i-1][j-1]+1
                max_num=max(max_num,dp[i][j])
    for i in range(len(str2)):
        for j in range(len(str1)):
            if dp[i][j]==max_num:
                res.append(str2[i-max_num+1:i+1])
    res.sort()
    for ans in res:
        print(ans)
a=input().split()
LCS(a[0],a[1])

本地没问题这里会报错不知道为啥

发表于 2020-01-11 00:20:52 回复(0)

查找字符串最长公共子串

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题