输入n个字符串(1<=n<=3*102,字符串总长度不超过103,只包含小写字母)
后面多次查询,每次查询输入两个数字x,y,输出第x个字符串和第y个字符串的最长公共前缀长度。(查询次数不超过102)
第1行输入一个整数n,代表字符串数量;
第2~n+1行,每行一个字符串;
第n+2行开始,每行输入两个整数a和b,代表需要计算公共前缀的字符串编号。
每次查询输出一行一个整数,表示两个字符串的最长公共前缀的长度
2 abc abe 1 2
2
def longestCommonPrefix(a,b): res = 0 if not a&nbs***bsp;not b: return '' n = min(len(a),len(b)) for i in range(n): if a[i]==b[i]: res +=1 else: return res return res n = int(input()) a =[] for i in range(n): a.append(input().strip()) while True: try: x,y = map(int,input().split()) print(longestCommonPrefix(a[x-1],a[y-1])) except: break
#include<iostream> #include<string> #include<vector> using namespace std; int str_len(const string& str1, const string& str2) { int index = 0; while (index < str1.size() && index < str2.size() && str1[index] == str2[index]) { index++; } return index; } int main() { int n; cin >> n; vector<string> v_str; for (int i = 0; i < n; i++) { string temp; cin >> temp; v_str.push_back(temp); } int a; int b; while (cin >> a >> b) cout << str_len(v_str[a - 1], v_str[b - 1]) << endl; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); String[] ss=new String[n]; scanner.nextLine(); for(int i=0;i<n;i++) ss[i]=scanner.nextLine(); while(scanner.hasNext()){ int a=scanner.nextInt(),b=scanner.nextInt(); System.out.println(count(ss[a-1],ss[b-1])); } } public static int count(String s1,String s2){ int num=0,n1=s1.length(),n2=s2.length(); while(num<n1&&num<n2){ if(s1.charAt(num)==s2.charAt(num)) num++; else return num; } return num; } }
n=int(input()) string=[] for i in range(n): string.append(input()) while True: try: a,b=map(int,input().split()) strA=string[a-1] strB=string[b-1] i=0 try: while strA[i]==strB[i]: i+=1 print(i) except: print(i) except: break
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.lang.String; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null) { // 获得字符串个数 int n = Integer.parseInt(line); String[] strs = new String[n]; // 读取字符串 for(int i = 0; i < n; i++) strs[i] = br.readLine(); // 查询字符串的最长公共前缀长度 while((line = br.readLine()) != null){ String[] ids = line.split(" "); int idx1 = Integer.parseInt(ids[0]); int idx2 = Integer.parseInt(ids[1]); System.out.println(solve(strs[idx1 - 1], strs[idx2 - 1]).length()); } } } // 求解两个字符串的最长公共前缀 private static String solve(String a, String b) { StringBuilder result = new StringBuilder(""); for(int i = 0; i < a.length(); i++){ if(i == b.length() || a.charAt(i) != b.charAt(i)) return result.toString(); result.append(a.charAt(i)); } return result.toString(); } }
#include<bits/stdc++.h> using namespace std; int main(){ int n,a,b; cin>>n; int k=n; vector<string> s(n); int i=0; while(n--){ cin>>s[i++]; } while(cin>>a>>b){ string str1,str2; if(a!=0&&b!=0){ str1=s[a-1]; str2=s[b-1]; } int res=0,k=0; while(str1[k]==str2[k]&&str1[k]!='\0'&&str2[k]!='\0'){ res++; k++; } cout<<k<<endl; } return 0; }
def func(a,b): m = min(len(a),len(b)) res = 0 for i in range(m): if a[i] == b[i]: res += 1 continue else: return res return res N = int(input()) data = [] for i in range(N): data.append(input().strip()) while True: try: cur = input().strip(' ').split(' ') i = int(cur[0]) - 1 j = int(cur[1]) - 1 print(func(data[i],data[j])) except: break
def longestCommonPrefix(a,b): res = 0 if not a&nbs***bsp;not b: return '' n = min(len(a),len(b)) for i in range(n): if a[i]==b[i]: res +=1 else: return res return res n = int(input()) a =[] for i in range(n): a.append(input().strip()) while True: try: x,y = map(int,input().split()) print(longestCommonPrefix(a[x-1],a[y-1])) except: break
n = int(input()) ls = [] while n: n-=1 ls.append(input()) while True: s = input().split() i = int(s[0])-1 j = int(s[1])-1 a = ls[i] b = ls[j] index = min(len(a),len(b)) end = index while True: if a[:index] != b[:index]: end = index index//=2 elif a[:index] == b[:index] and (end!=index and end-1!=index): index = (index+end)//2 else: print(index) break
n = int(input().strip()) ans = [] for i in range(n): tmp = str(input().strip()) ans.append(tmp) def fun(str1,str2): #str1 = ans[n1] (5144)#str2 = ans[n2] l1 = len(str1) l2 = len(str2) l_min = min(l1,l2) res = 0 for i in range(l_min): if str1[i]==str2[i]: res+=1 else: break return res while True: try: m, n = list(map(int, input().split())) print(fun(ans[m - 1], ans[n - 1])) except: break
def commonLength(str1,str2): res = 0 while str1 and str2 and str1.pop(0) == str2.pop(0): res +=1 return res if __name__ == '__main__': num = int(input()) strList = [] for i in range(num): strTmp = input() strList.append(strTmp) try: while True: idx = input() if not idx: break idx = list(map(int,idx.split())) str1 = list(strList[idx[0]-1]) str2 = list(strList[idx[1]-1]) res = commonLength(str1,str2) print(res) except: pass
import sys def match(s, x, y): s1 = s[x - 1] s2 = s[y - 1] shortlength = min(len(s1), len(s2)) res = 0 for i in range(shortlength): if s1[i] == s2[i]: res += 1 else: break return res n = int(input()) s = [] for i in range(n): s.append(input()) try: while True: line = sys.stdin.readline().strip()#或line = input(),在while循环中不知为何多行读取必须先将输入赋值给一个变量 if not line: break xy = list(map(int, line.split(' '))) x = xy[0] y = xy[1] res = match(s, x, y) print(res) except: pass
class Solution: def __init__(self, ch=[]): self.ch = ch def searchfirstword(self, id1, id2): ch1 = self.ch[id1-1] ch2 = self.ch[id2-1] for i in range(min(len(ch1), len(ch2))): if ch1[i] != ch2[i]: return i else: if i == min(len(ch1), len(ch2))-1: return i return 0 num_ch = input() n = int(num_ch) ch = [] for i in range(n): k = input() ch.append(k) num_search = input() func = Solution(ch) while num_search != 'q': num_search = num_search.split() ch_search_1 = int(num_search[0]) ch_search_2 = int(num_search[1]) # print(ch_search_1, ch_search_2) res = func.searchfirstword(ch_search_1, ch_search_2) print(res) num_search = input()没看出有什么错误_(:зゝ∠)_,奇怪了