algorithms icon indicating copy to clipboard operation
algorithms copied to clipboard

Add compute_z_array Function with Unit Tests

Open Simranstha045 opened this issue 1 year ago • 0 comments

PR Description:

This PR introduces the implementation of the compute_z_array function, which computes the Z-array for a given string in linear time, as well as comprehensive unit tests to verify its correctness.

Description of compute_z_array Function:

The compute_z_array function calculates the Z-array for a string, where each element at index i represents the length of the longest substring starting from index i that is also a prefix of the string.

Key Features:

  • Utilizes the Z-box technique to reduce unnecessary comparisons.
  • Processes the string in linear time.

Use case: The Z Algorithm is like a super-smart search tool that looks at parts of a string and tells you how much they match the beginning of the string. It's useful when you want to find patterns quickly, like searching for words in a long text, detecting DNA sequences, or even finding virus patterns in files. It does all this in a smart way, skipping unnecessary checks, so it's super fast!

Unit Tests for compute_z_array:

The following tests have been added to ensure robustness:

  • Basic Test Cases: Verifies correct Z-array generation for strings with repeating patterns (e.g., "aaaaa" and "ababa").
  • Edge Case Tests:
    • Strings with no prefix matches (e.g., "abcde").
    • Full match strings (e.g., "aaaa").
    • Mixed case strings with partial matches.
    • Single character strings.
    • Empty string input.

These unit tests ensure the function works as expected across a range of inputs, providing confidence in its correctness and edge-case handling.

All tests have been added under the unittest framework to maintain consistency with the existing test suite.

Simranstha045 avatar Oct 18 '24 11:10 Simranstha045