Checking whether a string is a substring of another string without using indexOf method

[Stephen Son]

Write a method that checks whether a string is a substring of another string. Write a test program that prompts the user to enter two strings, and check whether the first string is a substring of the second. Do not use indexOf or contains methods.

Here is my code:
import java.util.*;
import java.lang.String;

public class CheckingSubstring2 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("Please enter a String: ");
		String string1 = input.next();
		System.out.print("Please enter a second String: ");
		String string2 = input.next();
		if (isSubstring(string1, string2)) {
			System.out.println("The first string is a substring of the second.");
		} else {
			System.out.println("The first string is NOT a substring of the second.");
		}
	}	
	public static boolean isSubstring(String string1, String string2) {
		char c;
		char d;
		boolean match = true;
		for (int i = 0; i < string1.length(); i++) {
			c = string1.charAt(i);
			for (int j = 0; i < string2.length(); i++) {
				d = string2.charAt(i);
				if (c == d) {
					match = true;
				} else {
					match = false;
				}	
			}
		}
		return match;
	}
}

Here are some sample outputs from my program:

Please enter a String: ant
Please enter a second String: antarctica
The first string is a substring of the second.

Please enter a String: ant
Please enter a second String: tyrant
The first string is NOT a substring of the second.

The first output is correct. However the second output is wrong. "ant" is a substring of "tyrant". What is wrong with my code?

[Keith Rainey]

Take a look at your second loop... you're mixing your i and j counter vars


Ignore that... changing what I thought makes the first example break..

[Henry Wong]

Stephen Son wrote:
The first output is correct. However the second output is wrong. "ant" is a substring of "tyrant". What is wrong with my code?

Unfortunately, there seems to be a bit wrong with it -- you will have to add some debugging printouts to see what is going on -- as it doesn't do what you think it does.

For example, try "ant" and "alaska". You will see that the program reports that it matches.

Another example, try "texas" and "vermont". You will see that the program reports that it also matches.

Henry

[Stephen Son]

for (int j = 0; j < string2.length(); j++) {

@Keith Rainey I think that's right. I fixed up my i's and j's and it doesn't break.

@Henry Wong I tried those examples and the program reported that it matches. However, after fixing the i's and j's in my second loop, both examples do not report a match. With "ant" and "tyrant", it still does not work. What do you mean by debugging printouts? I've never heard of those.

[Raymond Tong]

Stephen Son wrote:What do you mean by debugging printouts? I've never heard of those.

inserting some printout (System.out.println) in your code to debug
e.g. you expected match to be true but false, you print the c and d variable

What is your substring comparison logic in English ?

[Stephen Son]

You mean like this:

if (c == d) {
	match = true;
} else {
	System.out.println(c + " " + d);
}	

My logic is I am going to compare the first character of string1 to each of the characters of string2. If a match is not found, the method returns false. If a match is found, then I will compare the second character of string1 to each of the characters of string2 and so on... Is my logic correct?

[Raymond Tong]

Stephen Son wrote:
My logic is I am going to compare the first character of string1 to each of the characters of string2. If a match is not found, the method returns false. If a match is found, then I will compare the second character of string1 to each of the characters of string2 and so on... Is my logic correct?

Forget about writing Java code first.
Your logic is checking that each character of string1 contains in string2.
Suppose string1 is abc, string2 is bca. Your logic would return true.

[Stephen Son]

Ok I fixed up my logic. My logic is I am going to compare the first character of string1 to each of the characters of string2. If a match is not found, the method returns false. If a match is found, then the second character of string1 will be compared to the character that succeeds the matching character of string2. If those don't match, the method returns false. If they do match, the program will continue and so on... Is it correct now?

[Paul Clapham]

That's much better. There are still a few details which aren't quite right, but you could start implementing that algorithm and then when failures occur, you will see what those details were.

[Stephen Son]

Ok I made some changes to my if else statment. Here's my code now:

import java.util.*;
import java.lang.String;

public class CheckingSubstring2 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("Please enter a String: ");
		String string1 = input.next();
		System.out.print("Please enter a second String: ");
		String string2 = input.next();
		if (isSubstring(string1, string2)) {
			System.out.println("The first string is a substring of the second.");
		} else {
			System.out.println("The first string is NOT a substring of the second.");
		}
	}	
	public static boolean isSubstring(String string1, String string2) {
		char c;
		char d;
		boolean match = true;
		for (int i = 0; i < string1.length(); i++) {
			c = string1.charAt(i);
			for (int j = 0; j < string2.length(); j++) {
				d = string2.charAt(j);
				if (c != d) {
					match = false;
				} else {
					match = true;
				}	
			}
		}
		return match;
	}
}

I tested "ant" and "tyrant", "ant" and "alaska", "texas" and "vermont", "abc" and "bca" and got the right output. I think my code is working properly. I can't think of any examples where the program won't work. If you seen anything else wrong with my code, let me know.

[Paul Clapham]

Ask it if "banana" is a substring of "ba-freaking-nana".

[Paul Clapham]

Ask it if "ash" is a substring of "bath".

[Paul Clapham]

Stephen Son wrote:My logic is I am going to compare the first character of string1 to each of the characters of string2. If a match is not found, the method returns false.

Your code doesn't do that. In this algorithm you treat the first character of string1 specially -- as you should -- but in your code you don't. It does the same thing for all characters of string1.

If a match is found, then the second character of string1 will be compared to the character that succeeds the matching character of string2. If those don't match, the method returns false. If they do match, the program will continue and so on.

Your code doesn't do that. There isn't anything there which looks for the character after the one you just looked at. It just goes through all characters in string2 every time.

[Stephen Son]

I tested both examples and both times the program says "The first string is a substring of the second."

Paul Clapham wrote:

Stephen Son wrote:My logic is I am going to compare the first character of string1 to each of the characters of string2. If a match is not found, the method returns false.

Your code doesn't do that. In this algorithm you treat the first character of string1 specially -- as you should -- but in your code you don't. It does the same thing for all characters of string1.

I thought it did. I thought these 2 lines did that.

                if (c != d) {  
                    match = false;

What would I change to get the code to do work correctly?

Paul Clapham wrote:

If a match is found, then the second character of string1 will be compared to the character that succeeds the matching character of string2. If those don't match, the method returns false. If they do match, the program will continue and so on.

Your code doesn't do that. There isn't anything there which looks for the character after the one you just looked at. It just goes through all characters in string2 every time.

I didn't realize that. I don't know how to do that. Would I add a third loop after "} else {" like this:

for (int k = d; k < string2.length(); k++) {

If not, then how do I get the method to look for the character it just looked at?

[Raymond Tong]

May be you could break down your logic to steps.
And put comment next to your codes about the "step" it implemented.

And as suggested above, add debugging printout. (Insert System.out.println without removing existing code)

[Stephen Son]

Raymond Tong wrote:May be you could break down your logic to steps.
And put comment next to your codes about the "step" it implemented.

And as suggested above, add debugging printout. (Insert System.out.println without removing existing code)

Even if I break down my logic into steps, I still don't know how to write code for each step. I read your explanation on debugging printout but I'm still not sure what it is. Can you show me an example?

[Paul Clapham]

Stephen Son wrote:I tested both examples and both times the program says "The first string is a substring of the second."

Okay. Do you not have anything to say about that? Was that correct or not? It isn't testing if you just print out some information, you have to ask yourself whether the information is correct.

Raymond Tong wrote:May be you could break down your logic to steps.
And put comment next to your codes about the "step" it implemented.

Exactly. Precisely.

And don't throw together the whole program all at once. Implement one step at a time and test. This was going to be your first step:

I am going to compare the first character of string1 to each of the characters of string2

So write some code which just does that and prints something, like which of the characters it matched.

[Stephen Son]

No, the output is not correct. For both examples, the first is not a substring of the second.
As for the first step, I have no idea what I'm doing wrong. That's why I asked "What would I change to get the code to do work correctly?".

[Henry Wong]

Stephen Son wrote:
Even if I break down my logic into steps, I still don't know how to write code for each step. I read your explanation on debugging printout but I'm still not sure what it is. Can you show me an example?

You won't actually know if you can write code for it, until you get it down to the steps first right? And if you can't it probably means that it is still too complicated and you need to break it down some more. The goal here is to write up the steps for how you would do it -- not the computer. After all, if you can't describe how you would do it, how would you be able to teach the computer to do it?

Henry

[Raymond Tong]

Stephen Son wrote:I read your explanation on debugging printout but I'm still not sure what it is. Can you show me an example?

char charOfString1 = 'a';
char charOfString2 = 'a';
charOfString2 = 'b'; // suppose some bug in codes
boolean findMatched = false;
if (charOfString1 == charOfString2) {
    findMatched = true;
} else {
    // Here are the debugging printout
    System.out.println("I am not suppose to be here. But why?");
    System.out.println("Show me the value of charOfString1 and charOfString2: " + charOfString1 + " and " + charOfString2);
    findMatched = false;
}

[Stephen Son]

This topic has been cross posted here.

@Henry Wong Ok I see. Here are the steps:
1)compare the first character of string1 to each of the characters of string2
2)If a match is not found, the method returns false
If a match is found, proceed to step 3
3)the second character of string1 will be compared to the character that succeeds the matching character of string2
4)If a match is not found, the method returns false
If a match is found, proceed to step 4
5)the third character of string1 will be compared to the character that succeeds the next matching character of string2
6)Repeat

@Raymond Tong Thanks, debugging printout wasn't covered in my java class. I will add them for now and delete them before I turn it in.

d and c have been switched in line 26. And debugging printout has been added.

import java.util.*;
import java.lang.String;

public class CheckingSubstring2 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("Please enter a String: ");
		String string1 = input.next();
		System.out.print("Please enter a second String: ");
		String string2 = input.next();
		if (isSubstring(string1, string2)) {
			System.out.println("The first string is a substring of the second.");
		} else {
			System.out.println("The first string is NOT a substring of the second.");
		}
	}	
	public static boolean isSubstring(String string1, String string2) {
		char c;
		char d;
		boolean match = true;
		for (int i = 0; i < string1.length(); i++) {
			c = string1.charAt(i);
			for (int j = 0; j < string2.length(); j++) {
				d = string2.charAt(j);
				if (d != c) {
					match = false;
					System.out.println("MATCH: N The value of c and d: " + c + " and " + d);	
				} else {
					System.out.println("MATCH: Y The value of c and d: " + c + " and " + d);
				}
				match = true;	
			}
		}
		return match;
	}
}

This is the output:

Please enter a String: ant
Please enter a second String: bath
MATCH: N The value of c and d: a and b
MATCH: Y The value of c and d: a and a
MATCH: N The value of c and d: a and t
MATCH: N The value of c and d: a and h
MATCH: N The value of c and d: n and b
MATCH: N The value of c and d: n and a
MATCH: N The value of c and d: n and t
MATCH: N The value of c and d: n and h
MATCH: N The value of c and d: t and b
MATCH: N The value of c and d: t and a
MATCH: Y The value of c and d: t and t
MATCH: N The value of c and d: t and h
The first string is a substring of the second.

How do I do the next step?

[Deepak Soni]

@Stephen Son as i looked at your code ..
it works only when first string is a sub string of second from begining...otherwise it will fail...

[Stephen Son]

@Deepak Soni Yeah I noticed that too.

I made some changes to my code and it seems to be working correctly. All the strings I've tested seem to work. However I'm not 100% certain my code is correct. Is there anything wrong with it?

import java.util.*;
import java.lang.String;

public class CheckingSubstring2 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("Please enter a String: ");
		String string1 = input.next();
		System.out.print("Please enter a second String: ");
		String string2 = input.next();
		if (isSubstring(string1, string2)) {
			System.out.println("The first string is a substring of the second.");
		} else {
			System.out.println("The first string is NOT a substring of the second.");
		}
	}	
	public static boolean isSubstring(String string1, String string2) {
		char c;
		char d;
		boolean match = true;
		int count = 1;
		int counter = 0;
		boolean matchFound = false;
		for (int i = 0; i < string1.length(); i++) {
			c = string1.charAt(i);
			//Part 2: This part determines if the characters following the 1st matching character are also matches
			if (matchFound == true) {
				for (int j = count + counter; j < string2.length(); j++) {
					d = string2.charAt(j);
					if (d != c) {
						System.out.println("MATCH2: N The value of c and d: " + c + " and " + d);	
						match = false;
					} else {
						counter++;
						System.out.println("MATCH2: Y The value of c and d: " + c + " and " + d + " " + counter);
						matchFound = true;
						break;
					}
				}
			}	
			//Part1: This part determines wheter the 1st character of string1 has a match in string2
			//If a match is found, Part 2 happens
			if (matchFound == false) {
				for (int k = 0; k < string2.length(); k++) {
					d = string2.charAt(k);	
					if (d != c) {
						count ++;
						System.out.println("MATCH: N The value of c and d: " + c + " and " + d + " " + count);	
						matchFound = false;
					} else {
						System.out.println("MATCH: Y The value of c and d: " + c + " and " + d + " " + count);
						matchFound = true;
						break;
					}	
				match = true;
				}	
			}	
		}
			return match;
	}
}

[Raymond Tong]

Stephen Son wrote:I made some changes to my code and it seems to be working correctly. All the strings I've tested seem to work. However I'm not 100% certain my code is correct. Is there anything wrong with it?

If you take "abc" and "bc", you expected to return "NOT" a substring but not the case.

There are 2 tips for you.
1) As soon as you know string1 is impossible to be a substring of string2, you could return false immediately without further checking.
2) When you find the (i)th char of string1 match (j)th char of string2, you should check against (i+1)th char and (j+1)th char of string2.

[Winston Gutkowski]

Raymond Tong wrote:

Stephen Son wrote:I made some changes to my code and it seems to be working correctly. All the strings I've tested seem to work. However I'm not 100% certain my code is correct. Is there anything wrong with it?

If you take "abc" and "bc", you expected to return "NOT" a substring but not the case.
There are 2 tips for you.
1) As soon as you know string1 is impossible to be a substring of string2, you could return false immediately without further checking...

@Stephen: I've noticed that in all your tests, you've assumed that string1 must be a substring of string2, yet you described the problem as: "Write a method that checks whether a string is a substring of another string". There is nothing intrinsically wrong with what you're doing (indeed, it's probably the best way to start), but I think you need to document the fact that you've put this interpretation on it.

Also: As Raymond pointed out, you're missing an extremely simple test that allows you to eliminate cases where string1 cannot be a substring of string2.

Winston

[Henry Wong]

Stephen Son wrote:@Henry Wong Ok I see. Here are the steps:
1)compare the first character of string1 to each of the characters of string2
2)If a match is not found, the method returns false
If a match is found, proceed to step 3
3)the second character of string1 will be compared to the character that succeeds the matching character of string2
4)If a match is not found, the method returns false
If a match is found, proceed to step 4
5)the third character of string1 will be compared to the character that succeeds the next matching character of string2
6)Repeat

Stephen,

I think you are trying to "hand wave" through the exercise. Or maybe even avoid it all together.

Take out a paper and pencil, take your instructions, and try to follow it to the letter. Pretend that you don't know what the purpose of the instructions are, and that someone else wrote it. You will realize that (1) some parts of those notes are vague, and (2) other parts of those notes are just wrong -- getting you wrong answers.

You need to get these instructions clear. And you need to get to the instructions that work. Otherwise, you just have broken instructions, that you are going to try to translate to code.

Henry

[Henry Wong]

Stephen Son wrote:This is the output:

Please enter a String: ant
Please enter a second String: bath
MATCH: N The value of c and d: a and b
MATCH: Y The value of c and d: a and a
MATCH: N The value of c and d: a and t
MATCH: N The value of c and d: a and h
MATCH: N The value of c and d: n and b
MATCH: N The value of c and d: n and a
MATCH: N The value of c and d: n and t
MATCH: N The value of c and d: n and h
MATCH: N The value of c and d: t and b
MATCH: N The value of c and d: t and a
MATCH: Y The value of c and d: t and t
MATCH: N The value of c and d: t and h
The first string is a substring of the second.

How do I do the next step?

That's the point of debugging -- to figure out what is happening, so that you can fix it. What does these log messages tell you? Is it useful? What information is missing? Basically, do you have enough information to understand what the computer is doing?

If you do, the next step is figure out where it went wrong, so that you can determine how to fix it.

If you don't, the next step is to add logging messages to get the information that you deem is missing.

Henry

[Stephen Son]

@Raymond Tong Oh I see. Thanks. "bc" is shorter than "abc". When string 2 is shorter than string 1, the method should return false. Ok I will add that to my code.

@Winston Gukowski What interpretation? If you didn't know, I actually wrote the problem. The problem in the book asks to use indexOf method. My teacher asked us not to use indexOf or contains method so I just reworded the problem from the book to meet her requirements. Yes, I'm missing a test to see if string2 is longer than string1. I will add that to my code.

@Henry Wong I'm not trying to avoid anything. I don't know why you think that. I rewrote the instructions and made them more clear.
0)check if string2 is longer than string1, if string2.length() > string1.length() proceed to step 1. If not, return false.
1)compare the first character of string1 to each of the characters of string2
2)If a match is never found, the method returns false
If a match is found eventually, count will record the position of the match. Break and proceed to Part2 of program
3)the second character of string1 will be compared to the character that succeeds the matching character of string2
4)If a match is not found, the method returns false
If a match is found, proceed to step 4, counter will record the position of the new match
and it will be added to count so that the loop will start at this position the next time.
5)the third character of string1 will be compared to the character that succeeds the next matching character of string2
6)Repeat until all characters of string1 have matched(return true) or until a match is not found(return false).

The messages tell me that the first character of string1 is being compared to each character of string2 and so on. Only the count/counter is missing so I added it to my code earlier. Yes I understand what the computer is doing. The loop should break after a match is found so I added that to my code earlier. What is the next step after that?

[Henry Wong]

Stephen Son wrote:@Henry Wong I'm not trying to avoid anything. I don't know why you think that.

Apologies. It is just that I was frustrated that you seem to be ignoring any instructions that seems to require more effort...

Stephen Son wrote:I rewrote the instructions and made them more clear.
0)check if string2 is longer than string1, if string2.length() > string1.length() proceed to step 1. If not, return false.
1)compare the first character of string1 to each of the characters of string2
2)If a match is never found, the method returns false
If a match is found eventually, count will record the position of the match. Break and proceed to Part2 of program
3)the second character of string1 will be compared to the character that succeeds the matching character of string2
4)If a match is not found, the method returns false
If a match is found, proceed to step 4, counter will record the position of the new match
and it will be added to count so that the loop will start at this position the next time.
5)the third character of string1 will be compared to the character that succeeds the next matching character of string2
6)Repeat until all characters of string1 have matched(return true) or until a match is not found(return false).

The messages tell me that the first character of string1 is being compared to each character of string2 and so on. Only the count/counter is missing so I added it to my code earlier. Yes I understand what the computer is doing. The loop should break after a match is found so I added that to my code earlier. What is the next step after that?

Which brings me back to my original instructions...

Henry Wong wrote:Take out a paper and pencil, take your instructions, and try to follow it to the letter. Pretend that you don't know what the purpose of the instructions are, and that someone else wrote it. You will realize that (1) some parts of those notes are vague, and (2) other parts of those notes are just wrong -- getting you wrong answers.

You need to get these instructions clear. And you need to get to the instructions that work. Otherwise, you just have broken instructions, that you are going to try to translate to code.

So, when you worked through it with a pencil and paper, did you find parts of the instructions that needed clarification? Did you find parts of the instructions that seem to not work?

And once you break it down so that it is clear, and proven on paper that it works, can you envision on how to break it into code?

Henry

[Winston Gutkowski]

Stephen Son wrote:@Winston Gukowski What interpretation? If you didn't know, I actually wrote the problem. The problem in the book asks to use indexOf method. My teacher asked us not to...

Your interpretation is that the program should check if the first string entered is a substring of the second. From the way you originally described it, it could just as easily be interpreted as meaning that the program should check if either string entered is a substring of the other.

Winston.

[Stephen Son]

@Henry Wong As for clarification, I can understand it well. Maybe other people would have difficulty understanding it. But everyone's brain works differently. The only flaw is that the loop breaks and returns false as soon as a match is not found in Part2, like "shaky" and "shkshaky". This was brought to my attention on another forum. I also notice that the loop will end if the last character of string2 is a match to the first character of string1 in the case of "abc" and "bca". Because "bca" ends with "a", there are no more characters left to compare. Yes I can sort of envision it into code. The program is really complex so it's really hard to envision.

@Winston Gutkowski I see what you mean now. Sorry I should have worded the problem better like this:

Write a method that checks whether a the first string is a substring of the second string. Write a test program that prompts the user to enter two strings, and check whether the first string is a substring of the second. Do not use indexOf or contains methods.
_________________________________________________________________________________________________________

Here is the most up to date version of my code:

import java.util.*;
import java.lang.String;

public class CheckingSubstring2 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("Please enter a String: ");
		String string1 = input.next();
		System.out.print("Please enter a second String: ");
		String string2 = input.next();
		if (isSubstring(string1, string2)) {
			System.out.println("The first string is a substring of the second.");
		} else {
			System.out.println("The first string is NOT a substring of the second.");
		}
	}	
	public static boolean isSubstring(String string1, String string2) {
		char c;
		char d;
		boolean match = true;
		int count = 1;
		int counter = 0;
		boolean matchFound = false;
		for (int i = 0; i < string1.length(); i++) {
			c = string1.charAt(i);
			if (string1.length() > string2.length()) {
				match = false;
				break;
			}
			//Part 2: This part determines if the characters following the 1st matching character are also matches
			if (matchFound == true) {
				for (int j = count + counter; j < string2.length(); j++) {
					d = string2.charAt(j);
					if (d != c) {
						System.out.println("MATCH2: N The value of c and d: " + c + " and " + d);	
						match = false;
					} else {
						counter++;
						System.out.println("MATCH2: Y The value of c and d: " + c + " and " + d + " " + counter);
						matchFound = true;
						break;
					}
				}
			}	
			//Part1: This part determines wheter the 1st character of string1 has a match in string2
			//If a match is found, Part 2 happens
			if (matchFound == false) {
				for (int k = 0; k < string2.length(); k++) {
					d = string2.charAt(k);	
					if (d != c) {
						count ++;
						System.out.println("MATCH: N The value of c and d: " + c + " and " + d + " " + count);	
						matchFound = false;
					} else {
						System.out.println("MATCH: Y The value of c and d: " + c + " and " + d + " " + count);
						matchFound = true;
						break;
					}	
				match = true;
				}	
			}	
		}
			return match;
	}
}

I told my professor I would send her the program today. I tried moving the breaks and adding another if statement. Some strings that didn't work before would work and other strings that did work before didn't work. I know it's not perfect but I am going to turn in my code like this. This topic is not resolved so I will not mark it as resolved. I'm not saying I'm giving up. I'm just saying it's time to turn it in. She is probably wondering why I haven't turned it in yet. This is the hardest java problem I had to do. No wonder it was on the very last homework assignment. Thank you to everyone who responded to this thread. I appreciate your help and in the process I have learned a lot. I probably won't be taking another java class in the future because this is really hard.