用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为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)
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)
#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; } }
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)); } } }
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) } }
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); } })();
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)
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();
有些偷懒的方法
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
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; } }
#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; }
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))
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); } } }
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))
#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()); }
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 { } } }输出结果顺序不一样,也会错?
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])本地没问题 这里会报错 不知道为啥