java - 字符串匹配两个字符串的前 n 个字母

Question

因此，对于我面临的问题，我想知道两个字符串“相同”的序列(从索引 0 开始)有多长 - 我认为仅举一个例子会更清楚；

• 如果两个字符串是“Yellowstone”和“Yelling”，我希望该方法返回 4 - 意思是，两个字符串的前 4 个字符匹配(“Yell”)

有没有比仅仅迭代这两个单词更(时间)高效的方法来解决这个问题？我可以使用某种内置方法吗？ (对于我的任务，我想避免导入任何自定义库)

Answer 1

我认为最快的方法是使用二进制搜索，这将为您提供 O(logn) 复杂度而不是 O(n)。这里n是最小字符串的长度。

二分查找的方法很简单。查找两个字符串中索引字符的相似性结尾。例如，如果 i 是您的索引，则检查 i+1 是否存在不相似字符，其中 i 索引处的字符相似。如果是这种情况，请返回 i 作为您的答案。否则继续在子范围内搜索。

编辑

添加函数以便更好地理解。

int lengthOfFirstSimilarCharacters(String str1, String str2) {
    int strlen1 = str1.length();
    int strlen2 = str2.length();
    if(strlen1 > strlen2){
        return lengthOfFirstSimilarCharacters(str2,str1);
    }
    int i = 0;
    int j = strlen1-1;
    while(i<=j){
        int mid = i + (j-i)/2;
        if(str1.charAt(mid) == str2.charAt(mid)) {
            if(mid+1<strlen1 && str1.charAt(mid+1) != str2.charAt(mid+1)){
                return mid+1;
            }
            i = mid+1;
        }else{
            j = mid-1;
        }
    }
    return i;
}