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...

In what way is the answer incorrect? Can you give us a few examples? — Keppil
– Keppil, Commented May 11, 2013 at 16:35
Enter the string: QWERTYQWERTYQWFDS Enter the sub string: QWE The character is available 3.0 times This is the out put for the above given inputs. — Dinithi De Silva
– Dinithi De Silva, Commented May 11, 2013 at 16:39

Sergey Kalinichenko · Accepted Answer · 2013-05-11 16:39:39Z

2

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.

answered May 11, 2013 at 16:39

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Dinithi De Silva Over a year ago

public void checkAvailability() { len=st.length(); for(int i=0;i<st.length()-substr.length();i++) { for(int j=0;j<substr.length();j++) { if( st.charAt(i+j)==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++; } } else { mismatch=true; break; } } } }

Dinithi De Silva Over a year ago

Is that the way you told? But I didn't get a solution.

Sergey Kalinichenko Over a year ago

@Dini88 That's better, but not quite right: the first if should check inequality !=, and there should be no second if. Take a look: link.

Dinithi De Silva Over a year ago

That works fine..Thanks. Can you tell me a way to get the number of times that the substring contains in the string?

Sergey Kalinichenko Over a year ago

@Dini88 There are two ways to produce an answer to this question. Consider an example: how many times xx is contained in xxxxxx? Both answers 3 and 5 are correct: answer 3 counts non-overlapping substrings, i.e. when each character could be part of no more than one match; answer 5 allows overlaps. For the answer with overlaps, increment a counter instead of println, and remove the second break; for the answer with no overlaps you would need to adjust i by length of substr, and remove the second break as well.

Collectives™ on Stack Overflow

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

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related