Java Review - Programming Project 2
Lab Name:String matching
Purpose:To review basic syntax by implementing a pattern matching algorithm.
Required Files:
Introduction: String matching is "The problem of finding occurrence(s) of a pattern string within another string or body of text." It is used in all sorts of applications from DNA mapping to searching for a word or phrase in a word processing document or web page.
Problem Description: Complete the following method in class Matcher:
/* pre:source != null, target != null
post:prints out number of character to character comparisons to standard output and all indices in source that are the starting point for the String target.
*/
public void matches(String source, String target)
{
Examples:
Example 1: If the source is "aaaabaaaa" and the target is "aaa" the method would print out the following:
Number of comparisons when searching for "aaa"
in "aaaabaaaa" was 18
Matches occurred at indices 0 1 5 6
How are there 18 comparisons? Remember, you are counting up the number of character to character comparisons, whether they are a match or not. So initially lining up target with the first character in source gives:
aaaabaaaa
aaa
From above, this results in three comparisons (a-a, a-a, a-a). Now, slide the target down 1 spot in the source.
aaaabaaaa
aaa
From above, this results in three more comparisons (a-a, a-a, a-a) for a total of 6. Slide the target down another spot.
aaaabaaaa
aaa
From above, this results in three more comparisons (2 matches and 1 mismatch, a-a, a-a, a-b) for a total of 9.
Slide the target down another spot.
aaaabaaaa
aaa
From above, this results in two more comparisons (1 match and 1 mismatch, a-a, a-b) for a total of 11. (Why stop comparing and slide when a mismatch occurs?) Slide the target down another spot.
aaaabaaaa
aaa
From above, this results in two more comparisons (1 mismatch, a-b) for a total of 12. Slide the target down another spot.
aaaabaaaa
aaa
From above, this results in three more comparisons (a-a, a-a, a-a) for a total of 15. Slide the target down another spot.
aaaabaaaa
aaa
This is the last legal alignment and results in three more comparisons (a-a, a-a, a-a) for a total of 18.
Limitations: The only methods you may use from the String class are charAt and length. You are essentially replicating the functionality of the indexOf method which is a very useful exercise.
Hints:
Java Review - Programming Project 2
1