第二题 - A23467.最长公共前缀 题目链接跳转：A23467.最长公共前缀 这道题也非常的简单。题目要求求出两个数字的最长公共前缀的长度。例如字符串 interview 和 interrupt 的最长公共前缀就是 inter，所以应该输出 555。 具体地，在遍历的时候判断两个字符串中同一个索引对应的两个字符是否相等，如果相等就将答案长度增加，否则就停止循环就可以了。PS：在遍历的过程中需要注意不要让索引超限。 本题的 AC 代码如下： 本题的 Python 代码如下： 本算法的时间复杂度约为 O(min⁡(lena,lenb))O(\min(\text{lena}, \text{lenb}))O(min(lena,lenb))。其中，lena 与 lenb 分别代表读入进来的两个字符串的长度。

题目解析 我们可以使用一个变量 iii 从 000 开始依次比较两个字符串的当前字符，直到遇到不相等的字符，或者其中一个字符串遍历完毕停下来，此时 iii 就是两个字符串的最长公共前缀的长度。 C++ AC代码： Python AC代码：

由于是求公共前缀，所以遍历次数是两个字符串中长度较短的，同样一旦对应字符不相等就直接结束。

/* 以上这种方法完全不行：请不要采用！ #include <iostream> #include <string> using namespace std; int main(){ string m,n; cin >> m >> n; for(int i = 0;i < m.size();i++){ if(n[i] != m[i]){ cout << i; break; } } return 0; }*/ #include <bits/stdc++.h> using namespace std; int main(){ string a,b; int sum = 0; cin >> a >> b; for (int i = 0;i < a.size();i++){ if (a[i] == b[i]){ sum++; }else break; }cout << sum; }

发现最长公共前缀的长度在 [0,min⁡(∣S∣,∣T∣)][0,\min(\left|S\right|,\left|T\right|)][0,min(∣S∣,∣T∣)] 之间。我们只需进行顺序遍历，碰到不匹配就退出即可。

按照题意模拟，从开头遍历，一直到第一个不相等的元素 C++: Python: 时间复杂度：O(min⁡(N,M))O(\min(N,M))O(min(N,M))