首页 > 试题广场 >

字符串最长公共前缀

[编程题]字符串最长公共前缀
  • 热度指数:3100 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入n个字符串(1<=n<=3*102,字符串总长度不超过103,只包含小写字母)
后面多次查询,每次查询输入两个数字x,y,输出第x个字符串和第y个字符串的最长公共前缀长度。(查询次数不超过102


输入描述:

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

第2~n+1行,每行一个字符串;

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



输出描述:
每次查询输出一行一个整数,表示两个字符串的最长公共前缀的长度
示例1

输入

2
abc
abe
1 2

输出

2
网上大佬的代码,可供学习。case通过率100%
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


发表于 2020-08-11 17:55:12 回复(0)
#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;
}

编辑于 2020-04-22 14:32:25 回复(0)
#include<iostream>
#
include<string>
#include<vector>
#
include<algorithm>

using namespace std;
void com1(string str1, string str2)
{
    int s1, s2;
    
    int m = 0;
    
    for (int i = 0; i < min(str1.length(), str2.length()); i++)
    {
        if (str1[i] == str2[i])
        {
            m++;

        }
        else
            break;
    }
    cout << m << endl;

}


int main()
{
    int n;
    cin >> n;
    vector<string> str(n);

    for (int i = 0; i < n; i++)
        cin >> str[i];
    int k = 0;
    while (k < 100)
    {
        int x = 0, y = 0;
        
        cin >> x >> y;
        if (x != 0 && y != 0)
        {
            com1(str[x - 1], str[y - 1]);
            k++;
            //x = 0; y = 0;
        }
        else
            break;
    }
}
发表于 2020-03-25 18:56:19 回复(0)
分别对比两个字符串,很简单的思路
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;
    }
}


发表于 2020-03-12 22:54:26 回复(0)
大无语事件,多次查询真的离谱,输入太难搞了
发表于 2022-03-19 14:03:34 回复(0)
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

发表于 2021-03-12 09:54:34 回复(0)
这道题的输入输出真是弄得我头疼
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();
    }
}


发表于 2020-10-15 17:04:20 回复(0)
#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;
}

发表于 2020-08-26 23:30:10 回复(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


发表于 2020-08-21 16:32:26 回复(0)
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

发表于 2020-08-12 22:48:54 回复(0)
using namespace std;
#include <iostream>
#include <string>
#include <vector>
int main()
{
    int i=0, n;
    cin >> n;
    string s;
    vector<string> str[1000];
    for(i=0;i<n;i++)
    {
        cin >> s;
        str[i].push_back(s);
    }
    int x, y;
    int num;
    string a,b;
    while (cin >> x && cin >> y)
    {
        num = 0;
        a = str[x - 1][0];
        b = str[y - 1][0];
        for (i = 0;; i++)
        {
            if (a[i] != b[i]||a[i]=='\0'||b[i]=='\0')
                break;
            else
                num++;
        }
        cout << num << endl;

    }
}
发表于 2020-08-11 10:53:37 回复(0)
import sys
n=int(input())
string=[]
for i in range(n):
    string.append(input())
ab=sys.stdin.readlines()
for i in ab:
    a,b=list(map(int,i.split()))
    l=0
    for j in range(min(len(string[a-1]),len(string[b-1]))):
        if string[a-1][j]!=string[b-1][j]:
            break
        l+=1
    print(l)
发表于 2020-05-06 11:08:28 回复(0)
我想知道我哪里错了
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

发表于 2020-04-20 12:17:47 回复(0)
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

发表于 2020-04-16 09:02:48 回复(0)
try:
    n =int(input())
    nums =[]
    fori inrange(n):
        nums.append(input())
    ifn ==1:
        print(len(nums[0]))
    a1, b1 =input().split()
    whilea1 andb1:
        a =nums[int(a1)-1]
        b =nums[int(b1)-1]
        print(a, b)
        la =len(a)
        lb =len(b)
        count =0
        ifla < lb:
            fori inrange(la):
                ifa[i] ==b[i]:
                    count +=1
                else:
                    print(count)
                    break
        else:
            forj inrange(lb):
                ifa[j] ==b[j]:
                    count +=1
                else:
                    print(count)
                    break
        try:
            a1, b1 =input().split()
        except:
            break
exceptException as e:
    print(e)
发表于 2020-03-20 13:03:11 回复(0)
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)
#include<iostream>
#
include<algorithm>
#include <vector>
#
include <string>
#include<sstream>
using namespace std;
int maxpre(string a, string b) {
    int res = 0;
    int si***(a.size(), b.size());
    for (int i = 0; i < size; i++) {
        if (a[i] == b[i]) {
            res++;
        }
        else {
            break;
        }
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    cin.ignore();
    vector<string> strs(n);
    vector<vector<int>> pair;
    vector<int> row;
    int a,b;
    string line, word;
    for (int i = 0; i < n;i++) {
        getline(cin, strs[i]);
    }
    while (getline(cin, line))
    {
        //直到输入长度为0的时候,结束读入
        if (line.size() == 0) break;
        //使用istringstream 获取读入的一行
        istringstream record(line);
        //读取每一行中的单个数据
        while (record >> word)
            row.push_back(atoi(word.c_str()));
        pair.push_back(row);
        row.clear();
    }
    for (int i = 0; i < pair.size(); i++) {
        int res = maxpre(strs[pair[i][0]-1], strs[pair[i][1]-1]);
        cout << res << endl;

    }
    return 0;
    
}
发表于 2020-03-18 16:26:42 回复(0)
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

发表于 2020-03-11 01:18:02 回复(0)
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()
没看出有什么错误_(:зゝ∠)_,奇怪了
发表于 2020-03-10 02:36:32 回复(0)