Find given sequence of tekst in a string without using contains

[torkolort]

Hi,

I have a school assignment where I need to check if one string is a substring in another string. However, we are not allowed to do any string-based comparison, we are only allowed to compare the ASCII values. So the way I do it now is to call the String.toCharArray() on both strings and use loops. However it looks pretty ugly, and I figure there has to be a better way to do this. This is what I have, and it is working but I wish to do it in a better way.

public boolean deltekst(String tekst1, String tekst2){
		if(equals(text1, text2))
			return false;
		if(bigger(text2, text1))
			return false;
		
		char[] list1 = text1.toCharArray();
		char[] list2 = text2.toCharArray();
		
		boolean substring = false;
		
		for(int i = 0; i < list1.length; i++){
			if((int)list1[i] == (int)list2[0]){
				for(int j = 1; j < list2.length; j++){
					if((i + j) >= list1.length)
						break;
					else{
						int ascii1 = (int)list[i + j];
						int ascii2 = (int)list[j];
						if(ascii1 != ascii2)
							break;
						else if(j == list2.length - 1)
							substring = true;
					}
				}
					
			}
			
		}
		return substring;
	}

Thanks in advance.

[JeffGrigg]

There's a lot to be said for using something that is simple and obviously correct.

There is also a lot to be said for testing. I recommend automated testing using JUnit. Example: Should 'deltekst("abc", "abc")' return true? Does it?

[Taywin]

If you are asking for an algorithm, Knuth-Morris-Pratt algorithm is a good algorithm to search a substring in another string (http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm). You can search for other algorithm as well, but this algorithm is very easy to understand to me.

[torkolort]

There's a lot to be said for using something that is simple and obviously correct.

There is also a lot to be said for testing. I recommend automated testing using JUnit. Example: Should 'deltekst("abc", "abc")' return true? Does it?

Sorry, I see I forgot to translate the parameter names and method name. It should be

public boolean substring (String text1, String text2)

We are told to use native language in our naming conventions, which I think is total bullcrap as it only leads to confusion and misunderstandings.

Anyway, we are also only allowed to use basic Java code, and they want us to use booleans and loops to solve this. So that's what I did and it does work, but I feel like I may have over complicated things a bit. And I'm not sure if they even approve of the break keyword. So we are definitely not allowed to use JUnit testing.

@Taywin
Yeah, the solution should probably be an algorithm, I'll have to look more into that one.

[JamesCherrill]

Given the requirements, what you are doing is not bad. Obviously there are a number of little tweaks and tunings that could be done (eg there's no need to convert your chars to ints), but nothing fundamental. Some proper testing will flush out any actual mistakes. You're on the right lines; keep going!

[JeffGrigg]

So we are definitely not allowed to use JUnit testing.

I would have really strong opinions about an instructor or manager who said that their people should not test their work. It might even involve shouting. :icon_evil:

Anyway, we are also only allowed to use basic Java code, and they want us to use booleans and loops to solve this.

I don't think this would forbid using JUnit. "You're not allowed to use libraries or other 3rd party tools" would. But technically, that would forbid using an IDE to develop the code or an operating system to run it, too.

[torkolort]

Yeah I definitely agree. The assigment emphasizes only to use skills aquired so far in the course, which just barely cover the basics. But then again, the intention is obviously to make the students understand the fundamentals without "cheating". Using JUnit would perhaps not be considered as "cheating", at least I don't think so. But funny enough, using any IDE is actually forbidden at this point, and NOTEPAD is used for development.

To be honest, I'm not in the course and this is not my task. I'm just helping a friend out because he was struggling with this one. But I've been where he is now, programming in notepad. And I'm never gonna do that again. I use Eclipse when I help him out.

While I generally understand the approach they have on this type of tasks, I do not understand why the students are forced to code in notepad the first months. It's painful enough as it is to learn a whole new language. It's like if a French teacher would make the students carve rock in grammar lessons.

[JeffGrigg]

Anyway, we are also only allowed to use basic Java code, and they want us to use booleans and loops to solve this. ... Yeah, the solution should probably be an algorithm, I'll have to look more into that one.

I think that the restriction not to use arrays (and presumably not to use collection classes) will prevent using most common algorithms. You'd need to precompute some array of data for most algorithms.

[JeffGrigg]

Given the requirements, what you are doing is not bad. Obviously there are a number of little tweaks and tunings that could be done (eg there's no need to convert your chars to ints), but nothing fundamental. Some proper testing will flush out any actual mistakes. You're on the right lines; keep going!

"Dittos." (IE: I agree with everything James says.)

Be sure to check boundary conditions, such as empty strings and one character strings. There are several bugs in the code posted above. :-/

Consider using the "charAt" method on string. [This has nothing to do with bugs, but it might help simplify your code.]

[JeffGrigg]

... But then again, the intention is obviously to make the students understand the fundamentals without "cheating". ... But funny enough, using any IDE is actually forbidden at this point, and NOTEPAD is used for development.

..., I do not understand why the students are forced to code in notepad the first months. ...

I sometimes teach classes. I see the value of doing things "by hand" before tools -- so that you'll understand what the tools are doing for you. But I think that a lot of instructors take it too far. Personally, I say that when students have done it "by hand" three times, then they probably understand it, and so can move on to use tools that do it for them. I strive to end at a state of using modern tools productively, as one would in a real work environment.

[torkolort]

I agree, that sounds like a reasonable approach. More instructors should think like that.

[torkolort]

The teacher(well not teacher, it's the student assistant who corrects these) actually failed my friend on this assigment.

He said that we were not allowed to compare strings or chars, only numeric values. I said that doesn't make any sense as a char represents a numeric value, and casting it to int is just an unnecessary step that only results in more lines of code and more memory usage. Am I correct here?

He also said don't use arrays, it's not included in the pensum and makes things more complicated. I don't know how else to do this task.

[JeffGrigg]

I did suggest using '.charAt' instead of pulling the arrays out of the String instances. I have to agree with the assistant on that one.

I would also point out that the code, as posted, contains several bugs. (...after one makes the obvious changes needed to make it compile. ;-)

"The char data type is a single 16-bit Unicode character. It has a minimum value of '\u0000' (or 0) and a maximum value of '\uffff' (or 65,535 inclusive)." -- http://download.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

Oracle seems to think that the 'char' primitive data type holds values that can be interpreted as numeric values. The whole "casting char to int" thing, while it is not wrong, leaves a bad taste in my mouth.

[torkolort]

I actually overlooked the post where you proposed the use of charAt. That seems like a better approach yes.

[JamesCherrill]

... Oracle seems to think that the 'char' primitive data type holds values that can be interpreted as numeric values.

And why shouldn't they? In case of doubt the Java Language Specification is the definitive document. Here's (some of) what it has to say on this subject (my emphasis):

The numeric types are the integral types and the floating-point types.
The integral types are byte, short, int, and long, whose values are 8-bit, 16-bit,
32-bit and 64-bit signed two's-complement integers, respectively, and char, whose
values are 16-bit unsigned integers representing UTF-16 code units
...
The values of the integral types are integers in the following ranges:
• For byte, from -128 to 127, inclusive
• For short, from -32768 to 32767, inclusive
• For int, from -2147483648 to 2147483647, inclusive
• For long, from -9223372036854775808 to 9223372036854775807, inclusive
• For char, from '\u0000' to '\uffff' inclusive, that is, from 0 to 65535
...
The Java programming language provides a number of operators that act on integral
values: [... < <= == != >= > + - / \ * ^ etc etc]

(Wxtracted from JLS section 4.2 Primitive Types and Values)

So the JLS makes it absolutely clear that chars are integral numeric types and that all the normal numeric operators can be used with them without any need to (or reason to) cast to int.