第一行输入一个长度为
、仅由小写字母组成的字符串
。
第二行输入一个长度为
、仅由小写字母组成的字符串
。
输出一个字符串,代表
和
的最长公共子串。如果存在多个答案,输出在较短串中最先出现的那个。
awaabb aawbb
aa
在这个样例中,
和
都是
和
的最长公共子串,但
在较短串
中首先出现,因此输出
。
abcdefghijklmnop abcsafjklmnopqrstuvw
jklmnop
while True: try: str1=input() str2=input() #读取输入 if len(str1) < len(str2): #以str2 <str1 为前提编写,如果str2 >str1 则换位 str1,str2 = str2,str1 size = len(str2) #读取较小字符串长度(永远是str2) exit = False#终止loop重设 for i in range (len(str2)): #每次size从大到小逐渐-1 for ii in range (len(str2)-size+1): #移动size大小的方块 n = str1.find(str2[ii:(size+ii)]) #以步长为一遍历size大小方块找寻相同项 if n != -1:#找到相同 print(str2[ii:(size+ii)]) exit = True#用于跳出大循环 break#跳出本循环 size = size -1#size减小 if exit == True: break#跳出大循环 except: break
import sys def dp_func(short_str, long_str): dp = [[0 for i in range(len(long_str)+1)] for j in range(len(short_str)+1)] # dp[i][j] = d[i-1][j-1] + 1 mmax = 0 start = 0 for i in range(1, len(short_str)+1): for j in range(1, len(long_str)+1): if short_str[i-1] == long_str[j-1]: dp[i][j] = dp[i-1][j-1] + 1 if dp[i][j] > mmax: mmax = dp[i][j] start = i - mmax return short_str[start:mmax+start] ''' s1 = input() s2 = input() if len(s1) < len(s2): print(dp_func(s1, s2)) else: print(dp_func(s2, s1)) ''' while True: try: s1 = input() s2 = input() if len(s1) < len(s2): print(dp_func(s1, s2)) else: print(dp_func(s2, s1)) except: break
def func(s1, s2): start = 0 max_len = 0 for i in range(len(s1)): if s1[i] in s2: # 注意,j可以从i+max_len+1开始 for j in range(i+max_len+1, len(s1)+1): if s1[i:j] in s2: start = i max_len = j-i else: break return s1[start:max_len+start] while True: try: s1 = input() s2 = input() # 让s1为较短的字符串 if len(s1) > len(s2): s1, s2 = s2, s1 print(func(s1, s2)) except: break
while True: try: str1 = input() str2 = input() if len(str1) <= len(str2): short = str1 long = str2 else: short = str2 long = str1 mutual = '' for left in range(len(short)): for right in range(left + 1, len(short) + 1): if (short[left:right]) in long: if len(short[left:right]) > len(mutual): mutual = short[left:right] print(mutual) except EOFError: break
while True: try: a, b = input(), input() a, b = (a, b) if len(a)<=len(b) else (b, a) dp = [] for i in range(len(a)+1): dp.append([0] * (len(b)+1)) longest, r_index = 0, 0 for i in range(1, len(a)+1): for j in range(1, len(b)+1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 if dp[i][j] > longest: longest = dp[i][j] r_index = i print(a[r_index-longest:r_index]) except: break
# 2020年11月17日15:12:44 while True: try: str1 = input() str2 = input() # 确定短字符串和长字符串,以及短字符串长度 len1, len2 = map(len, [str1, str2]) if len1<len2: short_str = str1 long_str = str2 min_len = len1 else: short_str = str2 long_str = str1 min_len = len2 # 从短字符串的长度开始递减搜索公共子串,stop为停止搜索标志位 length = min_len stop = 0 while length>0: for i in range(min_len-length+1): if long_str.find(short_str[i:i+length]) != -1: print(short_str[i:i+length]) stop = 1 break if stop==1: break else: length -= 1 except: break
while True: try: s1 = input() s2 = input() lenth = 0 s_list = [] if len(s1)>len(s2): s1, s2 = s2, s1 for i in range(len(s1)): for j in range(i+1, len(s1)+1): temp = s1[i:j] if temp in s2 and j-i>lenth: s_list.append(temp) lenth = j-i print(s_list[-1]) except: break
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
while True: try: a_l = input() b_l = input() max_l ='' min_l ='' if len(a_l)>=len(b_l): max_l = a_l min_l = b_l else: max_l = b_l min_l = a_l n = len(min_l) outs ='' while n > 0: if n == len(min_l) and min_l in max_l: outs =min_l break else: for i in range(len(min_l)): #一开始少了一个判断导致超过字符串长度会出现1个字符 if (i+n)<len(min_l): x = min_l[i:i+n] if x in max_l: outs = x break if outs!='': break else: n -= 1 print(outs) except: break题目不难,调试半天,一直以为我退出循环的地方错了,后来发现,当i+n超过 最大长度,会输出1-2个字符的片段,提前匹配上,很尴尬
while True: try: s1 = input() s2 = input() short, long = (s1, s2) if len(s1) < len(s2) else (s2, s1) repeat = '' for i in range(len(short)): for j in range(len(short)): if short[i:j + 1] in long and j + 1 - i > len(repeat): repeat = short[i:j + 1] print(repeat) except: break
import re while True: try: a, b = input(), input() if len(a) > len(b): a, b = b, a c = a + '\n' + b L = [re.search(r'(.+)(?=.*\n.*\1)', c[i:]) for i in range(len(a))] L = [i.group() for i in L if i] print(max(L, key = len)) except: break
while True: try: n1=input().strip() n2=input().strip() list1=[] lenth1=len(n1) lenth2=len(n2) min_lenth=min(lenth1,lenth2) len1=0 result='' if lenth1>=lenth2: n1,n2=n2,n1 for i in range(min_lenth,1,-1): for j in range(min_lenth-i+1): n1_1=n1[j:j+i] if n2.find(n1_1)>=0: if i>len1: len1=i result=n1_1 print(result) except: break
长见识了
/*矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0*/ def getLCS(string1 , string2): matrix = [[0 for i in range(len(string2)+1)] for j in range(len(string1)+1)] maxl = 0 p = 0 for n in range(len(string1)): for m in range(len(string2)): if string1[n] == string2[m]: matrix[n+1][m+1] = matrix[n][m] + 1 if matrix[n+1][m+1] > maxl: maxl = matrix[n+1][m+1] p = n + 1 return string1[p-maxl:p] while True: try: string1 = input() string2 = input() print(getLCS(string2,string1)) except: break