Java: how String.contains(string) function works in java?

Question

I know the brute force approach with the time complexity of n*m (m is length of first string and n is the length of the other one) for testing if an string contains another one, however, I'm wondering to know if there is better solution for it?

boolean contains(String input,String search)

Answer 1

You can look at the source:

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

Answer 2

I'm wondering to know if there is better solution for it?

There are lots of algorithms for simple string searching; see the Wikipedia String Search page. The page includes complexity characterizations ... and references.

The standard Java java.lang.String implementation uses naive search under the hood. Some of the algorithms on the Wikipedia page that have better complexity for the search phase, but require non-trivial setup. I expect that the Sun/Oracle engineers have done extensive empirical testing and found that naive search works best on average over a wide range of real-world applications.

---

Finally ...

I know the brute force approach with the time complexity of O(n*m)

In fact, that is the worst case complexity. The average complexity is O(n). Consider this:

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;
}

The worst case happens with inputs like "AAA..." and "AAA...B". (The dots denote repetition.)

But in the average case (e.g. randomly generated input strings) you won't have an "almost match" for str2 at every position of str1. The inner loop will typically break in the iteration.