Member Avatar for GeekTool 
public static void main(String[] args) {

        String searchMe 
           = "Look for a substring in me";
        String substring = "sub";
        boolean foundIt = false;

        int max = searchMe.length() - 
                  substring.length();

    test:
        for (int i = 0; i <= max; i++) {
            int n = substring.length()
            int j = i;
            int k = 0;
            while (n-- != 0) {
                if (searchMe.charAt(j++)
                    != substring.charAt(k++)) {
                    continue test;
                }
            }
            foundIt = true;
                break test;
        }
        System.out.println(foundIt ?
            "Found it" : "Didn't find it");
    }

In this code, i have some questions:
1) While int max is declared, why is substring.length() is subtracted from searchMe.length() ?
2) What does "test:" stand for ? What if it does not exist ?
3 Actually, can you make a detailed explanation please ?

  • 4 Contributors
  • 7 Replies
  • 502 Views
  • 1 Hour Discussion Span
  • Latest Post Latest Post by deceptikon

Dani AI

Generated

This is a hand-written substring search: the outer loop tries every possible start position and the inner loop compares characters one-by-one. Key roles of the variables are: i = candidate start index in searchMe; max = last valid start so the pattern fits; j and k walk the text and pattern during a comparison; n is a countdown equal to the pattern length.

max is searchMe.length() - substring.length() because, with 0-based indexes, a pattern of length P can only start at indices 0..S-P (S = text length). Allowing i past that point would make charAt try to read beyond the end and throw an exception. As pointed out, that prevents the out-of-bounds case.

The label test: names the for-loop. continue test inside the inner loop immediately jumps to the next iteration of that labeled for-loop (skipping the rest of the current iteration), and break test exits that for-loop entirely. That is why a mismatch inside the inner while can skip directly to the next i without extra flags. and touched on this; labels are legal but uncommon—most code uses a small boolean or an inner break for readability.

A few micro-details that often confuse beginners: while (n-- != 0) uses post-decrement, so the loop runs exactly substring.length() times (the test uses the old value and then decrements). charAt(j++) and charAt(k++) compare characters then advance j/k after the access. Also note the posted snippet has a missing semicolon at int n = substring.length() which will prevent compilation.

A clearer, label-free equivalent is:

boolean found = false;
for (int i = 0; i <= search.length() - pattern.length(); i++) {
    boolean match = true;
    for (int j = 0; j < pattern.length(); j++) {
        if (search.charAt(i + j) != pattern.charAt(j)) { match = false; break; }
    }
    if (match) { found = true; break; }
}

This manual algorithm is O(S*P). For production code prefer the built-in indexOf/contains, and for very large inputs consider faster algorithms (KMP, Boyer-Moore). Stepping through either version in a debugger makes the variable roles and the control flow obvious.

Recommended Answers

All 7 Replies

Member Avatar for stultuske

where did you get this code? it's very inefficïënt, there's a standard method that does this for you.
next, don't just copy paste code here, since you don't understand it, it's obvious that you didn't write it yourself. start by saying what you think it does, and we'll correct you if you're wrong.

Member Avatar for Sky Diploma

1) While int max is declared, why is substring.length() is subtracted from searchMe.length() ?

Let us take an example,(and think that we donot have the subtraction of lengths )
you wish to find sub-string "xy" within a string of "abcx";
Your program starts working from a, the string doesn't match, then checks at b , and c and then finds x, because the first letters are matching it would want to go to the next character. But encounters the end of the array there by causing a Range Error (IndexOutOfBounds) .

By subtracting the lengths, you now declare that you will only need to search till abc, and effectively will not need to look over the next string.

2) What does "test:" stand for ? What if it does not exist ?

"test" represents a label. Learn more about labels here ()

3) Actually, can you make a detailed explanation please?

Try to look over the example in post 1 to understand about the flow

Member Avatar for GeekTool

I took this code from oracle's website. Of course, i have an idea about this code. But, i did not understand some parts. Also, i don't know anybody other than you to ask my questions. People around me don't even know how to use computer. For me, you are the only way to learn this language. Even if you don't want to care about my questions, i just want to thank all of you guys. I have learned everything from you.

Member Avatar for deceptikon

  1. If the search string is "abcdefg" and the search key is "xyz", there's no point searching beyond 'e' because a shorter search string than the key is guaranteed to not match.

  2. test is an abritrary label for the break statement. If it doesn't exist, the continue and break statements won't know where to jump to. Read up on the goto statement, it's a better way to get introduced to unconditional jumps.

  3. Step through the code in a debugger and you'll find it easier to wrap your head around exactly what's going on. I'm not sure anyone will be willing to hold your hand through the entire algorithm, simple as it is.

Member Avatar for stultuske

it has nothing to do with not caring about your questions, having you give your ideas first, forces you to go into it, and think it over a bit more. even if your answer is wrong, it will be easier to understand the right answer when it is given, and it will be easier for you to understand.

on our side, it just means it 'll be easier for us to explain, and we're not just explaining it to someone who 'll just copy-paste our answers on their homework, but has actually bothered to put some effort in it for him(/herself), which motivates us a lot more to actually pot the effort in it.

Member Avatar for GeekTool

on our side, it just means it 'll be easier for us to explain, and we're not just explaining it to someone who 'll just copy-paste our answers on their homework, but has actually bothered to put some effort in it for him(/herself), which motivates us a lot more to actually pot the effort in it.

This is not my homework. I am 15 years old. I am learning java just because i like computer. If i was in university, i would know anybody else to ask my questions, but where i live is really uneducated, and maybe i am one of the few people who speak english. I have learned english by myself and now i want to learn java by myself. Of course i want you to be motivated to answer my questions, but i just want you to be more tolerant.

Edited by GeekTool
Member Avatar for deceptikon

This is not my homework. I am 15 years old. I am learning java just because i like computer.

"Homework" in this case is meant in the more general sense of something that you'd benefit from putting effort into rather than simply being handed explanations and solutions. Experts don't become experts by having everything explained to them, they become experts by not depending on others to do their thinking.

This isn't to say that we won't help you along, but especially if you're doing this as a hobby because you enjoy it, we're less tolerant of apparent laziness in the learning process.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.