Check whether string contains sub string, without using the java predefined methods

Question

I need to find whether a given sub string contains within a given string.But the constraint is I cannot use any predefined Java methods. I have tried as follows.

public void checkAvailability()
{
    len=st.length();
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<substr.length();j++)
        {
            if(st.charAt(i)==substr.charAt(j))
            {
                if(j!=substr.length()-1 && i!=st.length()-1)
                {
                    if(st.charAt(i+1)==substr.charAt(j+1))
                    {
                        available=true;
                        //j++;
                        count++;
                    }
                }
            }
        }
    }
    if(available)
    {
        System.out.println("The character is available " + count + " times");
    }
    else
    {
        System.out.println("The character is not availabe");
    }
}

But it doesn't give the correct answer. Can somebody help please?

Thank you in advance...

Answer 1

There are a few mistakes in your code - I'll describe an algorithm without writing the code to avoid spoiling the learning exercise for you:

• The outer loop needs to go from 0 to st.length()-substr.length()
• The inner loop needs to check st.charAt(i+j) and substr.charAt(j)
• The inner loop needs to stop as soon as you find a mismatch; set a mismatch flag, and break
• If the inner loop completes without finding a mismatch, then i is the position of the first match.

Note that this is the most straightforward algorithm. It does not perform well when the st is long, and substr has lots of "false positives" In general, you can do better than that, for example, by using the KMP algorithm.