KMP String Matching Algorithm in Java

Student: Sadenov Ernar Group: SE-2430

Overview

This project implements the Knuth–Morris–Pratt (KMP) string matching algorithm in Java. The algorithm efficiently finds all occurrences of a pattern string within a text string in linear time.

The implementation includes three types of test cases:

1. Short string
2. Medium-length string
3. Long string (the pattern repeated 30 times)

This allows us to observe how the algorithm behaves under different conditions.

---

How It Works

KMP Algorithm

KMP avoids redundant comparisons by using a Longest Prefix Suffix (LPS) array:

• LPS[i] stores the length of the longest proper prefix of the pattern that is also a suffix of the substring pattern[0…i].
• When a mismatch occurs, the algorithm uses the LPS array to skip characters in the text instead of starting over from the next character.

The search process works as follows:

1. Compare characters of the text and the pattern.

2. If characters match, move both pointers forward.

3. If a mismatch occurs:

   • Use the LPS array to shift the pattern efficiently.
   • Continue comparison without re-checking matched characters.

4. When the pattern pointer reaches the end, a full match is found. Store the index and continue searching.

---

Code Structure

• Main Method (main): Initializes three test strings (short, medium, long) and patterns. Calls runTest() for each test.

• runTest(String text, String pattern): Executes the KMP search for a given text and pattern. Prints:

  • Text length
  • Pattern
  • Match positions
  • Total number of matches

• kmpSearch(String text, String pattern): Main KMP search function. Returns an array of starting indices of all matches.

• buildLPS(String pattern): Builds the LPS array for the pattern, used to skip redundant comparisons.

---

Input / Output Examples

Example 1 — Short string

Text:

ababcabcababd

Pattern:

abab

Output:

Matches at: 0 8
Total matches: 2

---

Example 2 — Medium string

Text:

aaaaaa

Pattern:

aa

Output:

Matches at: 0 1 2 3 4 5
Total matches: 6

---

Example 3 — Long string (pattern repeated 30 times)

Text length: 300 characters Pattern:

Algorithms

Output:

Matches at: 0 10 20 30 40 50 ... 290
Total matches: 30

---

Time and Space Complexity

Part	Time Complexity	Space Complexity
Build LPS array	O(m)	O(m)
KMP search	O(n)	O(k) (matches)
Total	O(n + m)	O(m + k)

Where:

• n = length of the text
• m = length of the pattern
• k = number of matches found

The algorithm guarantees linear time performance, even with repeated patterns.

---

Features

• Works for short, medium, and long strings.
• Uses ArrayList to store all match positions dynamically.
• Fully 0-based indexing for positions.
• Efficient: avoids unnecessary character comparisons using LPS.
• Easy to read and modify for educational purposes.

---

Notes

• The long string test demonstrates the efficiency of KMP on repetitive data.
• The code is fully self-contained — no input files needed. Test cases are defined in main.
• Can be easily adapted to read from user input or files if required.