codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
199 stars 270 forks source link

Added Z-function implementation #523

Closed CarolLuca closed 1 year ago

CarolLuca commented 1 year ago

I added an implementation of the Z-function of a string (also known as the Z-algorithm).

codecov[bot] commented 1 year ago

Codecov Report

Merging #523 (55a7ae2) into main (1aa53bf) will increase coverage by 0.011%. The diff coverage is 100.000%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #523 +/- ## ============================================= + Coverage 98.546% 98.558% +0.011% ============================================= Files 32 32 Lines 4059 4092 +33 ============================================= + Hits 4000 4033 +33 Misses 59 59 ``` | [Impacted Files](https://codecov.io/gh/codezonediitj/pydatastructs/pull/523?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj) | Coverage Δ | | |---|---|---| | [pydatastructs/strings/algorithms.py](https://codecov.io/gh/codezonediitj/pydatastructs/pull/523?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj#diff-cHlkYXRhc3RydWN0cy9zdHJpbmdzL2FsZ29yaXRobXMucHk=) | `100.000% <100.000%> (ø)` | | [![Impacted file tree graph](https://codecov.io/gh/codezonediitj/pydatastructs/pull/523/graphs/tree.svg?width=650&height=150&src=pr&token=mZMqq5ubAu&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj)](https://codecov.io/gh/codezonediitj/pydatastructs/pull/523?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj)
czgdp1807 commented 1 year ago

See, https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/523/blob/pydatastructs/strings/algorithms.py. L206 and L231 are not tested. When query = "", do we even need to do any kind of processing. In KMP we just do, return DynamicOneDimensionalArray(int, 0) if, text or query is empty. Why can't we do that in your implementation?

CarolLuca commented 1 year ago

See, app.codecov.io/gh/codezonediitj/pydatastructs/pull/523/blob/pydatastructs/strings/algorithms.py. L206 and L231 are not tested. When query = "", do we even need to do any kind of processing. In KMP we just do, return DynamicOneDimensionalArray(int, 0) if, text or query is empty. Why can't we do that in your implementation?

I see that the case is treated. The _z_vector() function doesn't do this because the actual vector it is often used also without a query, but for the _z_function(), I see I implemented the case when the lengths of the strings are zero. If I'm wrong please correct me, I might have missed something.