algorithms
algorithms copied to clipboard
Add compute_z_array Function with Unit Tests
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.