THINK FIRST·CODE LATER

← All labs

Finding a pattern: naive search versus KMP

Problem

Write PatternSearch, which reads pairs of lines — a text, then a pattern — and finds all the positions where the pattern occurs (overlapping occurrences included), with two algorithms, counting the character comparisons of each.

  1. Naive: try every starting position and compare character by character. Up to n × m comparisons.
  2. Knuth–Morris–Pratt: first build the failure table of the pattern — fail[k] is the length of the longest proper prefix of pattern[0..k] that is also a suffix of it. During the search, after a mismatch, the pattern is shifted according to the table and the text index never moves back. About n + m comparisons.

For the input

the cat sat on the mat with the other cat
the
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaaab
abababababab
abab
hello world
xyz

the program prints

"the" in a text of 41 characters: found at [0, 15, 28, 33]
  naive 52 comparisons, KMP 47 comparisons, same result: true
"aaaaaaaab" in a text of 41 characters: found at [32]
  naive 297 comparisons, KMP 88 comparisons, same result: true
"abab" in a text of 12 characters: found at [0, 2, 4, 6, 8]
  naive 24 comparisons, KMP 15 comparisons, same result: true
"xyz" in a text of 11 characters: found at []
  naive 9 comparisons, KMP 13 comparisons, same result: true

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d6-8-data-1.txt

the cat sat on the mat with the other cat
the
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaaab
abababababab
abab
hello world
xyz
What your program must print for d6-8-data-1.txt
"the" in a text of 41 characters: found at [0, 15, 28, 33]
  naive 52 comparisons, KMP 47 comparisons, same result: true
"aaaaaaaab" in a text of 41 characters: found at [32]
  naive 297 comparisons, KMP 88 comparisons, same result: true
"abab" in a text of 12 characters: found at [0, 2, 4, 6, 8]
  naive 24 comparisons, KMP 15 comparisons, same result: true
"xyz" in a text of 11 characters: found at []
  naive 9 comparisons, KMP 13 comparisons, same result: true

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d6-8-data-1.txt

Windows PowerShell does not understand <:

Get-Content d6-8-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.