java - Java：String.contains(string) 函数如何在 java 中工作？

Question

我知道用于测试字符串是否包含另一个字符串的时间复杂度的蛮力方法n*m (m is length of first string and n is the length of the other one)，但是，我想知道是否有更好的解决方案？

boolean contains(String input,String search)

Answer 1

您可以查看源代码：

public boolean contains(CharSequence s) {
    return indexOf(s.toString()) > -1;
}

Answer 2

我想知道是否有更好的解决方案？

有很多用于简单字符串搜索的算法；请参阅 Wikipedia字符串搜索页面。该页面包括复杂性特征......和参考资料。

标准 Javajava.lang.String实现在底层使用朴素搜索。Wikipedia 页面上的一些算法在搜索阶段具有更高的复杂性，但需要非常重要的设置。我希望 Sun/Oracle 工程师进行了广泛的实证测试，并发现朴素搜索在广泛的实际应用程序中平均效果最好。

---

最后 ...

我知道时间复杂度为O(n*m)

事实上，这是最坏情况的复杂性。平均复杂度为O(n). 考虑一下：

boolean bruteForceMatch (String str1, String str2) {
    for (int i = 0; i < str.length(); i++) {
        boolean matches = true;
        for (int j = 0; j < str2.length(); j++) {
            if (i + j >= str.length || 
                str1.charAt(i + j) != str2.charAt(j)) {
                matched = false;
                break;
            }
        }
        if (matched) {
            return true;
        }
    }
    return false;
}

最坏的情况发生在像“AAA...”和“AAA...B”这样的输入上。（点表示重复。）

但在一般情况下（例如随机生成的输入字符串），您不会str2在str1. 内部循环通常会break在迭代中。

Answer 3

有没有更好的办法？取决于你认为什么是“更好”。另一种方法是使用Pattern。但是，用户体验会有什么不同？它是否足够相关？

如果您真的想使用最佳选项，请通过足够的迭代自己尝试这两个选项。

Answer 4

这是我的解决方案：

static boolean contain(String input,String search)
{
    int[] searchIn = new int[search.length()];
    searchIn[0] = 0;
            //searchIn keep track of repeated values on search sting
            //so if the search string is "abcabd" then the corresponding searchIn is
            //0 0 0 1 2 0
    int k = 0;
    for(int i=1;i<search.length();i++)
    {
        if(search.charAt(i)== search.charAt(k))
        {
            searchIn[i] = ++k; 
        }
        else 
        {
            k =0;
            searchIn[i] = k;
        }       
    }
    int i=0;
    int j=0;

    while(i<=input.length()-1 && j<=search.length()-1)
    {
        if(input.charAt(i) == search.charAt(j))
        {
            i++;
            j++;
        }
        else
        {
            j = searchIn[j-1];
            if(i==input.length()-1)
                i++;
        }
    }
    if(j==search.length())
        return true;
    else return false;
}