One of the most widely used Web browser functions is the search utility. You probably know how it works. You type in a keyword and click on a button, and it returns with a list of Web pages that contain the keyword.
Subsection7.4.1Search Algorithm
Suppose you were writing a browser in Java. How would you implement this function? Of course, we don’t know yet how to read files or Web pages, and we won’t cover that until Chapter 11. But, for now, we can write a method that will search a string for all occurrences of a given keyword. That’s at least part of the task that the browser’s search engine would have to do.
So we want a method, keywordSearch(), that takes two String parameters, one for the string that’s being searched, and the other representing the keyword. Let’s have the method return a String that lists the number of keyword occurrences, followed by the index of each occurrence.
For example, if we asked this method to find all occurrences of is in “This is a test,” it should return the string “2: 2 5” because there are two occurrences of is, one starting at index 2 and the other at index 5 in the string.
The algorithm for this method will require a loop, because we want to know the location of every occurrence of the keyword in the string. One way to do this would be to use the indexOf() method to search for the location of substrings in the string. If it finds the keyword at index N, it should record that location and then continue searching for more occurrences starting at index \(N+1\) in the string. It should continue in this way until there are no more occurrences.
Algorithm7.4.1.Keyword search.
Suppose S is our string and K is the keyword.
Initialize a counter variable and result string.
Set Ptr to the indexOf() the first occurrence of K in S.
While (Ptr != -1)
Increment the counter
Insert Ptr into the result string
Set Ptr to the next location of the keyword in S
Insert the count into the result string
Return the result string as a String
As this pseudocode shows, the algorithm uses a while loop with a sentinel bound. The algorithm terminates when the indexOf() method returns a \(-1\text{,}\) indicating that there are no more occurrences of the keyword in the string.
Translating the pseudocode into Java gives us the method shown in Listing 7.4.2. Note how string concatenation is used to build the resultStr . Each time an occurrence is found, its location (ptr) is concatenated to the right-hand side of the resultStr. When the loop terminates, the number of occurrences (count) is concatenated to the left-hand side of the resultStr.
/**
* Pre: s and keyword are any Strings
* Post: keywordSearch() returns a String containing the
* number of occurrences of keyword in s, followed
* by the starting location of each occurrence
*/
public String keywordSearch(String s, String keyword)
{
String resultStr = "";
int count = 0;
int ptr = s.indexOf(keyword);
while (ptr != -1) {
++count;
resultStr = resultStr + ptr + " ";
ptr = s.indexOf(keyword, ptr + 1);// Next occurrence
}
resultStr = count + ": " + resultStr;// Insert the count
return resultStr; // Return as a String
} // keywordSearch()
Listing7.4.2.The keywordSearch() method.
Subsection7.4.2Testing and Debugging
What test data should we use for the keywordSearch() method? One important consideration in this case is to test that the method works for all possible locations of the keyword within the string. Thus, the method should be tested on strings that contain keyword occurrences at the beginning, middle, and end of the string. We should also test the method with a string that doesn’t contain the keyword. Such tests will help verify that the loop will terminate properly in all cases.
Given these considerations, Table 7.4.3 shows the tests that were made. As you can see from these results, the method did produce the expected outcomes. While these tests do not guarantee its correctness, they provide considerable evidence that the algorithm works correctly.
Table7.4.3.Testing the keywordSearch() method.
Test Performed
Expected Result
keywordSearch("this is a test","is")
2: 2 5
keywordSearch("able was i ere i saw elba","a")
4: 0 6 18 24
keywordSearch("this is a test","taste")
0:
Principle7.4.4.EFFECTIVE DESIGN: Test Data.
In designing test data to check the correctness of a string searching algorithm, it’s important to use data that test all possible outcomes.
ExercisesSelf-Study Exercise
1.Keyword search.
Run the code below to confirm the first result of our manual trace. Add additional calls to keywordSearch() to confirm the other results. Then experiment with your own search strings.
