Implemented Suffix Tree Data Structure (#11554)
* Implemented KD-Tree Data Structure
* Implemented KD-Tree Data Structure. updated DIRECTORY.md.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Create __init__.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Replaced legacy `np.random.rand` call with `np.random.Generator` in kd_tree/example_usage.py
* Replaced legacy `np.random.rand` call with `np.random.Generator` in kd_tree/hypercube_points.py
* added typehints and docstrings
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* docstring for search()
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Added tests. Updated docstrings/typehints
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* updated tests and used | for type annotations
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* E501 for build_kdtree.py, hypercube_points.py, nearest_neighbour_search.py
* I001 for example_usage.py and test_kdtree.py
* I001 for example_usage.py and test_kdtree.py
* Update data_structures/kd_tree/build_kdtree.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update data_structures/kd_tree/example/hypercube_points.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update data_structures/kd_tree/example/hypercube_points.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Added new test cases requested in Review. Refactored the test_build_kdtree() to include various checks.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Considered ruff errors
* Considered ruff errors
* Apply suggestions from code review
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update kd_node.py
* imported annotations from __future__
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Implementation of the suffix tree data structure
* Adding data to DIRECTORY.md
* Minor file renaming
* minor correction
* renaming in DIRECTORY.md
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Considering ruff part-1
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Considering ruff part-2
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Considering ruff part-3
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Considering ruff part-4
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Considering ruff part-5
* Implemented Suffix Tree Data Structure.
Added some comments to my files in #11532, #11554.
* updating DIRECTORY.md
* Implemented Suffix Tree Data Structure.
Added some comments to my files in #11532, #11554.
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: Ramy-Badr-Ahmed <Ramy-Badr-Ahmed@users.noreply.github.com>
2024-09-28 15:37:00 +02:00
|
|
|
# Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed)
|
|
|
|
|
# in Pull Request: #11554
|
|
|
|
|
# https://github.com/TheAlgorithms/Python/pull/11554
|
|
|
|
|
#
|
|
|
|
|
# Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request
|
|
|
|
|
# addressing bugs/corrections to this file.
|
|
|
|
|
# Thank you!
|
|
|
|
|
|
|
|
|
|
from data_structures.suffix_tree.suffix_tree import SuffixTree
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def main() -> None:
|
|
|
|
|
"""
|
|
|
|
|
Demonstrate the usage of the SuffixTree class.
|
|
|
|
|
|
|
|
|
|
- Initializes a SuffixTree with a predefined text.
|
|
|
|
|
- Defines a list of patterns to search for within the suffix tree.
|
|
|
|
|
- Searches for each pattern in the suffix tree.
|
|
|
|
|
|
|
|
|
|
Patterns tested:
|
|
|
|
|
- "ana" (found) --> True
|
|
|
|
|
- "ban" (found) --> True
|
|
|
|
|
- "na" (found) --> True
|
|
|
|
|
- "xyz" (not found) --> False
|
|
|
|
|
- "mon" (found) --> True
|
|
|
|
|
"""
|
|
|
|
|
text = "monkey banana"
|
|
|
|
|
suffix_tree = SuffixTree(text)
|
|
|
|
|
|
|
|
|
|
patterns = ["ana", "ban", "na", "xyz", "mon"]
|
|
|
|
|
for pattern in patterns:
|
|
|
|
|
found = suffix_tree.search(pattern)
|
|
|
|
|
print(f"Pattern '{pattern}' found: {found}")
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
if __name__ == "__main__":
|
|
|
|
|
main()
|
