Back to Repositories

Testing Rabin-Karp String Matching Algorithm in javascript-algorithms

This test suite validates the Rabin-Karp string matching algorithm implementation in JavaScript, covering basic substring searches, large text processing, and Unicode character handling. The tests verify the algorithm’s ability to find pattern matches within various text scenarios and edge cases.

Test Coverage Overview

The test suite provides comprehensive coverage of the Rabin-Karp algorithm functionality, examining substring matching across different scenarios.

Basic substring matching with empty strings and single characters
Complex pattern matching in longer strings
Large text processing with multiple occurrences
UTF-16 symbol handling and Unicode support
Edge cases including non-matching patterns and special characters

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for organized test grouping and clear test case separation.

Implementation features include:

Modular test organization with distinct test scenarios
Extensive use of expect().toBe() assertions for precise match index verification
String concatenation handling for large text tests
Unicode character testing with explicit hex codes

Technical Details

Testing infrastructure includes:

Jest testing framework
ES6+ JavaScript syntax
Unicode character support testing
Import/export module system
String manipulation utilities

Best Practices Demonstrated

The test suite exemplifies several testing best practices for algorithm validation.

Comprehensive edge case coverage
Structured test organization with descriptive test cases
Progressive complexity in test scenarios
Clear separation of test concerns
Documentation of Unicode limitations

trekhleb/javascript-algorithms

src/algorithms/string/rabin-karp/__test__/rabinKarp.test.js

            
import rabinKarp from '../rabinKarp';

describe('rabinKarp', () => {
  it('should find substring in a string', () => {
    expect(rabinKarp('', '')).toBe(0);
    expect(rabinKarp('a', '')).toBe(0);
    expect(rabinKarp('a', 'a')).toBe(0);
    expect(rabinKarp('ab', 'b')).toBe(1);
    expect(rabinKarp('abcbcglx', 'abca')).toBe(-1);
    expect(rabinKarp('abcbcglx', 'bcgl')).toBe(3);
    expect(rabinKarp('abcxabcdabxabcdabcdabcy', 'abcdabcy')).toBe(15);
    expect(rabinKarp('abcxabcdabxabcdabcdabcy', 'abcdabca')).toBe(-1);
    expect(rabinKarp('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca')).toBe(12);
    expect(rabinKarp('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa')).toBe(11);
    expect(rabinKarp('^ !/\'#\'pp', ' !/\'#\'pp')).toBe(1);
  });

  it('should work with bigger texts', () => {
    const text = 'Lorem Ipsum is simply dummy text of the printing and '
    + 'typesetting industry. Lorem Ipsum has been the industry\'s standard '
    + 'dummy text ever since the 1500s, when an unknown printer took a '
    + 'galley of type and scrambled it to make a type specimen book. It '
    + 'has survived not only five centuries, but also the leap into '
    + 'electronic typesetting, remaining essentially unchanged. It was '
    + 'popularised in the 1960s with the release of Letraset sheets '
    + 'containing Lorem Ipsum passages, and more recently with desktop'
    + 'publishing software like Aldus PageMaker including versions of Lorem '
    + 'Ipsum.';

    expect(rabinKarp(text, 'Lorem')).toBe(0);
    expect(rabinKarp(text, 'versions')).toBe(549);
    expect(rabinKarp(text, 'versions of Lorem Ipsum.')).toBe(549);
    expect(rabinKarp(text, 'versions of Lorem Ipsum:')).toBe(-1);
    expect(rabinKarp(text, 'Lorem Ipsum passages, and more recently with')).toBe(446);
  });

  it('should work with UTF symbols', () => {
    expect(rabinKarp('a\u{ffff}', '\u{ffff}')).toBe(1);
    expect(rabinKarp('\u0000耀\u0000', '耀\u0000')).toBe(1);
    // @TODO: Provide Unicode support.
    // expect(rabinKarp('a\u{20000}', '\u{20000}')).toBe(1);
  });
});