Overview
This tutorial will explain string searching. You will learn the length() function and several string searching methods including Java's indexOf() and lastIndexOf() functions. You'll also learn the principle behind the naive search method.
Java Functions
The first function we'll learn is probably the one that you'll use most often, the length() function. This returns the number of characters in a string.
String name = "Cole"; int x = name.length(); // x is now 4
This is very useful for iterating through all of the characters in a string. You can run a for loop like this:
for(int i = 0; i < name.length(); i++) { System.out.print(name.charAt(i) + " "); // This will print "C o l e " }
Another helpful function when doing stimple searches is indexOf(). This function will search for a character or a string inside of another string, and you can even pass a start index as the second argument. It will return the index of the first occurence that matches. Here are a few examples of the function in action.
String animalName = "Bella Bear"; int x = animalName.indexOf('a'); // x is now 4 x = animalName.indexOf('a', 6); // x is now 8 x = animalName.indexOf("Be"); // now, x is 0 x = animalName.indexOf("Be", 2); // finally, x ends up as 6
The function lastIndexOf(), works the same way that indexOf() works, except it searches from right to left, thus finding the last occurence. This function can also search for characters and strings, and can take a starting index to search back from as the second argument.
x = animalName.lastIndexOf("Be"); // x is now 6
These functions should allow you to do some simple searches using Java.
Naive Search Method
This is the simplest algorithm you can program to perform string searching. The method will basically place our test string (string2)
at one end of the string to search (string1) and then see if there is a match. If not, string2 will move over one place and see if it
matches. This will continue until you either find a match, or try all locations of string2.
SUPERCALIFRAGILISTICEXPIALIDOCIOUS //string1
COW //string2
Does "COW" == "SUP" // no
Does "COW" == "UPE" // no
Does "COW" == "PER" // no
This will take forever and find no matches!
Let's write some quick code pseudocode for this algorithm. You should try to implement your own version.
int naiveSearch(string p,t): {Find string p in string t. Return its position, or -1 if not found} for i from 0 to Length(t) - Length(p) do j = 0 while j < Length(p) and p[j] = t[i+j] do j = j + 1 if j = Length(p) then return i return -1
This method is very slow. The built-in Java functions are programmed to search more quickly and should be used over this method. There are two other well known algorithms that are faster than this one known as Knuth-Morris-Pratt and Boyer-Moore. You will study these in Data Structures class, but will not likely run in to them during a TopCoder competition.
Challenge
Program
You will be given a String search as well as a String array info. You are to find the string search within each element
of info and then return a String array that contains two Strings. The first will be the element of info in which search
occurs with the lowest index, and the second will be the element of info in which search occurs with the highest index. If
search is not found in any of the elements of info, return {"NONE","NONE"}. If there is a tie for either category, return
the element that occurs last in info.
Sample Inputs:
'z' //search
{"zoo",
"animals",
"zebra"} //info
"tate" //search
{"tate center",
"state of georgia",
"potato",
"rehabilitate"} //info
"string" //search
{"for",
"more"} //info
Sample Outputs:
{"zebra", "zebra"}
{"tate center","rehabilitate"}
{"NONE","NONE"}
