字符串最长公共前缀

[编程题]字符串最长公共前缀

热度指数：3104 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入n个字符串（1<=n<=3*10²，字符串总长度不超过10³，只包含小写字母）

后面多次查询，每次查询输入两个数字x，y，输出第x个字符串和第y个字符串的最长公共前缀长度。（查询次数不超过10²）

输入描述:

第1行输入一个整数n，代表字符串数量；

第2~n+1行，每行一个字符串；

第n+2行开始，每行输入两个整数a和b，代表需要计算公共前缀的字符串编号。

输出描述:

每次查询输出一行一个整数，表示两个字符串的最长公共前缀的长度

示例1

输入

2
abc
abe
1 2

输出

算法知识视频讲解

Python

小橙子&

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

发表于 2020-08-21 16:32:26 回复(0)

Python

Jaylynn

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

发表于 2020-03-19 19:51:15 回复(0)