feat: add manacher's algorithm #1577

riti2409 · 2021-08-29T19:19:45Z

Description of Change

Checklist

Added description of change
Added file name matches File name guidelines
Added tests and example, test must pass
Added documentation so that the program is self-explanatory and educational - Doxygen guidelines
Relevant documentation/comments is changed or added
PR title follows semantic commit guidelines
Search previous suggestions before making a new one, as yours may be a duplicate.
I acknowledge that all my contributions will be made under the project's license.

Notes: This is an implementation of the Manacher's Algorithm which is used to find the longest substring in linear time.

b30wulffz

Looks good to me.

vid-7695 · 2021-08-29T19:33:06Z

strings/manacher_algorithm.cpp

+    assert(strings::manacher::manacher("abababc") == "ababa");
+    assert(strings::manacher::manacher("cbaabd") == "baab");
+    assert(strings::manacher::manacher("xacdedcax") == "xacdedcax");
+    assert(strings::manacher::manacher("xacddcax") == "xacddcax");


Add some test cases with Upper , Mixed, camel Case. Test Cases format seem to be repeativie.

strings/manacher_algorithm.cpp

shikhar-psyduck

LGTM

Panquesito7

Great work, @riti2409! Thanks for reviewing, @b30wulffz, @vid-7695, and @shikhar-psyduck. 🙂
Also, please fix clang-tidy warnings.

Panquesito7 · 2021-08-30T16:35:48Z

strings/manacher_algorithm.cpp

@@ -0,0 +1,165 @@
+/**
+ * @file
+ * @brief Implementation of the


Suggested change

* @brief Implementation of the

* @brief Implementation of

Panquesito7 · 2021-08-30T16:36:05Z

strings/manacher_algorithm.cpp

+#include <cassert>   // for asserting test cases
+#include <iostream>  // for IO operations


Suggested change

#include <cassert> // for asserting test cases

#include <iostream> // for IO operations

#include <cassert> /// for assert

#include <iostream> /// for IO operations

Panquesito7 · 2021-08-30T16:36:14Z

strings/manacher_algorithm.cpp

+#include <cassert>   // for asserting test cases
+#include <iostream>  // for IO operations
+#ifdef _MSC_VER
+#include <string>  // required for MS Visual C++


Suggested change

#include <string> // required for MS Visual C++

#include <string> /// required for MS Visual C++

Panquesito7 · 2021-08-30T16:36:27Z

strings/manacher_algorithm.cpp

+#ifdef _MSC_VER
+#include <string>  // required for MS Visual C++
+#else
+#include <cstring>


Add a one-line description here as in line 17.

Panquesito7 · 2021-08-30T16:36:59Z

strings/manacher_algorithm.cpp

+/**
+ * @brief A function that implements Manacher's algorithm
+ * @param prototype is the string where algorithm finds a palindromic substring.
+ * This string can contain any character except @ # &


Suggested change

* This string can contain any character except @ # &

* This string can contain any character except `@` `#` `&`

Panquesito7 · 2021-08-30T16:37:14Z

strings/manacher_algorithm.cpp

+int main() {
+    test();  // run self-test implementations
+    return 0;
+}


Suggested change

}

}

riti2409 · 2021-08-30T17:35:33Z

@Panquesito7 I have incorporated all the suggestions. Please review.

Panquesito7

Almost there! 😄

Panquesito7 · 2021-08-30T18:05:10Z

strings/manacher_algorithm.cpp

+
+#include <cassert>   /// for assert
+#include <iostream>  /// for IO operations
+#include <vector>    /// for vector STL


Suggested change

#include <vector> /// for vector STL

#include <vector> /// for std::vector STL

riti2409 · 2021-08-30T18:31:18Z

@Panquesito7 Done 😀

Panquesito7 · 2021-08-30T19:49:47Z

strings/manacher_algorithm.cpp

+                 // stuffed string). This value will be lower bound of half
+                 // length since single character is a palindrome in itself.
+
+        int bigger_center =


Consider using uint64_t for non-negative values (or their appropriate size: uint32_t, uint16_t, uint8_t) or int64_t for negative values. Check other parts of the code (reference). 🙂

@Panquesito7 Sure, Updated

strings/manacher_algorithm.cpp

Panquesito7

Awesome work, @riti2409! Thanks for your contribution! 😄👍🎉

Panquesito7

Oh, you just missed one thing: please fix clang-tidy warnings.

riti2409 · 2021-08-30T20:33:35Z

@Panquesito7 Compile checks for "Awesome CI Workflow / Compile checks (windows-latest) (pull_request)" failed to run because of some server issue in the VM. Is it possible to rerun the checks?
As per the logs it can be verified that freeglut download failed while setting up VM in Awesome CI Workflow for windows.

Edit: I am pushing a small commit to rerun the checks.

Panquesito7

Awesome work, @riti2409! It's been great for your first contribution here! Thank you; we hope you keep contributing. 😄 👍 🎉

ayaankhan98

LGTM 👍

riti2409 · 2021-08-31T17:54:21Z

@Panquesito7 Thanks for encouraging :)

riti2409 added 2 commits August 30, 2021 00:21

feat: add manacher algorithm in strings/

d78cfd8

fix: directory.md format

5b8a4d7

b30wulffz previously approved these changes Aug 29, 2021

View reviewed changes

vid-7695 previously approved these changes Aug 29, 2021

View reviewed changes

shikhar-psyduck previously approved these changes Aug 29, 2021

View reviewed changes

Panquesito7 added the enhancement New feature or request label Aug 30, 2021

Panquesito7 requested changes Aug 30, 2021

View reviewed changes

Panquesito7 added requested changes changes have been requested automated tests are failing Do not merge until tests pass labels Aug 30, 2021

fix: add test cases, fix clang-tidy warning, implement requested changes

6da2c55

riti2409 dismissed stale reviews from shikhar-psyduck, vid-7695, and b30wulffz via 6da2c55 August 30, 2021 17:33

riti2409 requested a review from Panquesito7 August 30, 2021 17:34

Panquesito7 reviewed Aug 30, 2021

View reviewed changes

fix: update comments

4932e05

b30wulffz previously approved these changes Aug 30, 2021

View reviewed changes

Panquesito7 removed the automated tests are failing Do not merge until tests pass label Aug 30, 2021

Panquesito7 reviewed Aug 30, 2021

View reviewed changes

strings/manacher_algorithm.cpp Show resolved Hide resolved

fix: update int to uint64_t, add suggested changes

e4c4585

riti2409 dismissed b30wulffz’s stale review via e4c4585 August 30, 2021 20:19

Panquesito7 approved these changes Aug 30, 2021

View reviewed changes

Panquesito7 requested changes Aug 30, 2021

View reviewed changes

Panquesito7 added the automated tests are failing Do not merge until tests pass label Aug 30, 2021

fix: update description

1fe42a4

riti2409 requested a review from Panquesito7 August 30, 2021 20:42

Panquesito7 removed the automated tests are failing Do not merge until tests pass label Aug 30, 2021

Panquesito7 approved these changes Aug 30, 2021

View reviewed changes

Panquesito7 added approved Approved; waiting for merge and removed requested changes changes have been requested labels Aug 30, 2021

Panquesito7 requested review from ayaankhan98 and mishraabhinn August 30, 2021 22:51

ayaankhan98 approved these changes Aug 31, 2021

View reviewed changes

ayaankhan98 merged commit 70868f2 into TheAlgorithms:master Aug 31, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: add manacher's algorithm #1577

feat: add manacher's algorithm #1577

riti2409 commented Aug 29, 2021 •

edited by gitpod-io bot

Loading

b30wulffz left a comment

vid-7695 Aug 29, 2021

shikhar-psyduck left a comment

Panquesito7 left a comment

Panquesito7 Aug 30, 2021

Panquesito7 Aug 30, 2021

Panquesito7 Aug 30, 2021

Panquesito7 Aug 30, 2021

Panquesito7 Aug 30, 2021

Panquesito7 Aug 30, 2021

riti2409 commented Aug 30, 2021

Panquesito7 left a comment

Panquesito7 Aug 30, 2021

riti2409 commented Aug 30, 2021

Panquesito7 Aug 30, 2021

riti2409 Aug 30, 2021

Panquesito7 left a comment

Panquesito7 left a comment

riti2409 commented Aug 30, 2021 •

edited

Loading

Panquesito7 left a comment

ayaankhan98 left a comment

riti2409 commented Aug 31, 2021

		#include <cassert> // for asserting test cases
		#include <iostream> // for IO operations

	#include <string> // required for MS Visual C++
	#include <string> /// required for MS Visual C++

	* This string can contain any character except @ # &
	* This string can contain any character except `@` `#` `&`

	#include <vector> /// for vector STL
	#include <vector> /// for std::vector STL

feat: add manacher's algorithm #1577

feat: add manacher's algorithm #1577

Conversation

riti2409 commented Aug 29, 2021 • edited by gitpod-io bot Loading

Description of Change

Checklist

b30wulffz left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

shikhar-psyduck left a comment

Choose a reason for hiding this comment

Panquesito7 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

riti2409 commented Aug 30, 2021

Panquesito7 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

riti2409 commented Aug 30, 2021

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Panquesito7 left a comment

Choose a reason for hiding this comment

Panquesito7 left a comment

Choose a reason for hiding this comment

riti2409 commented Aug 30, 2021 • edited Loading

Panquesito7 left a comment

Choose a reason for hiding this comment

ayaankhan98 left a comment

Choose a reason for hiding this comment

riti2409 commented Aug 31, 2021

riti2409 commented Aug 29, 2021 •

edited by gitpod-io bot

Loading

riti2409 commented Aug 30, 2021 •

edited

Loading