最长公共前缀｜字符串遍历

第二题 - A23467.最长公共前缀

题目链接跳转：A23467.最长公共前缀

这道题也非常的简单。题目要求求出两个数字的最长公共前缀的长度。例如字符串 interview 和 interrupt 的最长公共前缀就是 inter，所以应该输出 $5$。

具体地，在遍历的时候判断两个字符串中同一个索引对应的两个字符是否相等，如果相等就将答案长度增加，否则就停止循环就可以了。PS：在遍历的过程中需要注意不要让索引超限。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    string a, b;
    int lena, lenb, ans = 0;
    cin >> a >> b;
    lena = a.size(); lenb = b.size();
    // 循环终止条件取两个字符串长度的最小值，放置索引超限。
    for (int i=0; i<min(lena, lenb); i++){
        if (a[i] == b[i]){
            ans++;
        } else break;
    }
    cout << ans << endl;
    return 0;
}

本题的 Python 代码如下：

S = input(); T = input()

def longest_common_prefix_length(S, T):
    min_length = min(len(S), len(T))
    for i in range(min_length):
        if S[i] != T[i]:
            return i
    return min_length

print(longest_common_prefix_length(S, T))

本算法的时间复杂度约为 $O(\min(\text{lena}, \text{lenb}))$。其中，lena 与 lenb 分别代表读入进来的两个字符串的长度。