Back to Repositories

Testing Knuth-Morris-Pratt String Pattern Matching in javascript-algorithms

This test suite validates the Knuth-Morris-Pratt string matching algorithm implementation in JavaScript. It verifies the algorithm’s ability to find pattern positions within text strings, covering various edge cases and pattern matching scenarios.

Test Coverage Overview

The test suite provides comprehensive coverage of the KMP algorithm’s pattern matching capabilities.

Key areas tested include:

Empty string handling for both pattern and text
Single character matching
Pattern not found scenarios
Complex pattern matching with overlapping characters
Multiple occurrence patterns

Implementation Analysis

The testing approach employs Jest’s describe/it structure to organize test cases systematically. Each test case uses expect().toBe() assertions to verify exact position matching, with special attention to boundary conditions and edge cases. The implementation validates both successful matches and non-matching scenarios.

Technical patterns include:

Zero-based index validation
Negative index return checks
Pattern length variations

Technical Details

Testing infrastructure:

Framework: Jest
Test Type: Unit tests
Testing Style: Behavior-driven development (BDD)
Assertion Pattern: Expect statements
File Organization: Dedicated test directory structure

Best Practices Demonstrated

The test suite exemplifies strong testing practices through clear test case organization and comprehensive edge case coverage. Notable practices include:

Systematic test case progression from simple to complex
Clear input/output expectations
Boundary condition testing
Consistent assertion patterns
Focused test scenarios

trekhleb/javascript-algorithms

src/algorithms/string/knuth-morris-pratt/__test__/knuthMorrisPratt.test.js

            
import knuthMorrisPratt from '../knuthMorrisPratt';

describe('knuthMorrisPratt', () => {
  it('should find word position in given text', () => {
    expect(knuthMorrisPratt('', '')).toBe(0);
    expect(knuthMorrisPratt('a', '')).toBe(0);
    expect(knuthMorrisPratt('a', 'a')).toBe(0);
    expect(knuthMorrisPratt('abcbcglx', 'abca')).toBe(-1);
    expect(knuthMorrisPratt('abcbcglx', 'bcgl')).toBe(3);
    expect(knuthMorrisPratt('abcxabcdabxabcdabcdabcy', 'abcdabcy')).toBe(15);
    expect(knuthMorrisPratt('abcxabcdabxabcdabcdabcy', 'abcdabca')).toBe(-1);
    expect(knuthMorrisPratt('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca')).toBe(12);
    expect(knuthMorrisPratt('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa')).toBe(11);
  });
});