[FEATURE REQUEST] <Rabin-karp-algo>

[chaitanyakatore]

What would you like to Propose?

I would like to propose the Rabin-karp algorithm which is use to search pattern in give string using hash function.
this algorithm is efficient for searching pattern In string with Time complexity : O(m*n)

Issue details

• The Rabin-Karp algorithm is a string searching algorithm that efficiently finds all occurrences of a given pattern (substring) within a longer text (string)
  Example: text = "AABAACAADAABAABA"
  pattern = "AABA"
  this algorithm finds pattern of "AABA" in "AABAACAADAABAABA" if it's present return true else return false

• The algorithm relies on a hash function that converts substrings of the text and the pattern into numerical hash values

• Rabin-Karp slides a window of the pattern's length over the text, computing the hash value for each window

• The algorithm can efficiently find multiple occurrences of the pattern in the text.

Additional Information

please make this issue label under hacktoberfest and assign me this task

[nidheeshR]

Hi @chaitanyakatore. Appreciate in recommending this algorithm for addition. But do you think Knuth-Morris-Pratt (KMP) Algorithm would be a better alternative as is provides a way better time and space complexity response?

Time Complexity: O(n + m), where n is the length of the text and m is the length of the pattern.
Space Complexity: O(m) for the failure function (prefix function) table.

[stasim101]

Hi @nidheeshR / @chaitanyakatore,
I appreciate suggestions from both of you. However, these algorithms don't work efficiently for Strings having sizes greater than 16. Sentences and paragraphs can be searched more efficiently using Boyer Moore Algorithm.

[chaitanyakatore]

I know this algorithm have more time complexity than above mentioned algo but this also must be in repo so peoples do understand the different approach and solve accordingly problems based on their preferences what is your opinion about this @nidheeshR @stasim101

[nidheeshR]

I know this algorithm have more time complexity than above mentioned algo but this also must be in repo so peoples do understand the different approach and solve accordingly problems based on their preferences what is your opinion about this @nidheeshR @stasim101

@chaitanyakatore Considering this repo is all about algorithms and not about the best among them, I agree that this can be added to the repo.

[nidheeshR]

Hi @nidheeshR / @chaitanyakatore, I appreciate suggestions from both of you. However, these algorithms don't work efficiently for Strings having sizes greater than 16. Sentences and paragraphs can be searched more efficiently using Boyer Moore Algorithm.

Good call @stasim101 .Though Boyer Moore, Knuth Morris Pratt and Brute Force algorithm all has the same complexities, I am sure that Boyer Moore performs better in practice.

[Intruder9211]

Hi @chaitanyakatore #4652 . I think that the Rabin-Karp algorithm is a great idea to implement for string searching. It is a very efficient algorithm, and it has a number of advantages over other string searching algorithms, such as the Naive algorithm.

Here are some of the advantages of the Rabin-Karp algorithm: #4655

It is very efficient, with a time complexity of O(m*n), where m is the length of the pattern and n is the length of the text.
It can efficiently find multiple occurrences of the pattern in the text.
It is relatively easy to implement.
The main disadvantage of the Rabin-Karp algorithm is that it can be susceptible to false positives. This means that the algorithm may identify a substring of the text as the pattern, even if it is not actually the pattern. However, this can be mitigated by using a good hash function and by carefully comparing the hash values of the pattern and the substring.

Overall, I think that the Rabin-Karp algorithm is a great choice for implementing string searching in Bard. It is a very efficient and accurate algorithm, and it is relatively easy to implement.

I am happy to help you with the implementation of the Rabin-Karp algorithm in Bard. Please let me know if you have any questions or need any assistance.

[chaitanyakatore]

@Intruder9211 actually I already PR for this but still it is note merged

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!