Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
manacher_algorithm.cpp File Reference

Implementation of Manacher's Algorithm More...

#include <cassert>
#include <iostream>
#include <vector>
#include <cstring>
Include dependency graph for manacher_algorithm.cpp:

Namespaces

namespace  strings
 Algorithms with strings.
 
namespace  manacher
 Functions for Manacher's Algorithm implementation.
 

Functions

std::string strings::manacher::manacher (const std::string &prototype)
 A function that implements Manacher's algorithm.
 
static void test ()
 Self-test implementations.
 
int main ()
 Main function.
 

Detailed Description

Implementation of Manacher's Algorithm

Manacher's Algorithm is used to find the longest palindromic substring within a string in O(n) time. It exploits the property of a palindrome that its first half is symmetric to the last half, and thus if the first half is a palindrome, then last half is also a palindrome.

Author
Riti Kumari

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
171 {
172 test(); // run self-test implementations
173 return 0;
174}
static void test()
Self-test implementations.
Definition manacher_algorithm.cpp:150
Here is the call graph for this function:

◆ manacher()

std::string strings::manacher::manacher ( const std::string & prototype)

A function that implements Manacher's algorithm.

Parameters
prototypeis the string where algorithm finds a palindromic substring. This string can contain any character except @ # &
Returns
the largest palindromic substring
40 {
41 if (prototype.size() > 0) {
42 // stuffing characters between the input string to handle cases with
43 // even length palindrome
44 std::string stuffed_string = "";
45 for (auto str : prototype) {
46 stuffed_string += str;
47 stuffed_string += "#";
48 }
49 stuffed_string = "@#" + stuffed_string + "&";
50
51 std::vector<uint64_t> palindrome_max_half_length(
52 stuffed_string.size(),
53 0); // this array will consist of largest possible half length of
54 // palindrome centered at index (say i with respect to the
55 // stuffed string). This value will be lower bound of half
56 // length since single character is a palindrome in itself.
57
58 uint64_t bigger_center =
59 0; // this is the index of the center of palindromic
60 // substring which would be considered as the larger
61 // palindrome, having symmetric halves
62
63 uint64_t right = 0; // this is the maximum length of the palindrome
64 // from 'bigger_center' to the rightmost end
65
66 // i is considered as center lying within one half of the palindrone
67 // which is centered at 'bigger_center'
68 for (uint64_t i = 1; i < stuffed_string.size() - 1; i++) {
69 if (i < right) { // when i is before right end, considering
70 // 'bigger_center' as center of palindrome
71 uint64_t opposite_to_i =
72 2 * bigger_center -
73 i; // this is the opposite end of string, if
74 // centered at center, and having one end as i
75
76 // finding the minimum possible half length among
77 // the palindrome on having center at opposite end,
78 // and the string between i and right end,
79 // considering 'bigger_center' as center of palindrome
80 palindrome_max_half_length[i] = std::min(
81 palindrome_max_half_length[opposite_to_i], right - i);
82 }
83
84 // expanding the palindrome across the maximum stored length in the
85 // array, centered at i
86 while (stuffed_string[i + (palindrome_max_half_length[i] + 1)] ==
87 stuffed_string[i - (palindrome_max_half_length[i] + 1)]) {
88 palindrome_max_half_length[i]++;
89 }
90
91 // if palindrome centered at i exceeds the rightmost end of
92 // palindrome centered at 'bigger_center', then i will be made the
93 // 'bigger_center' and right value will also be updated with respect
94 // to center i
95 if (i + palindrome_max_half_length[i] > right) {
96 bigger_center = i;
97 right = i + palindrome_max_half_length[i];
98 }
99 }
100
101 // now extracting the first largest palindrome
102 uint64_t half_length = 0; // half length of the largest palindrome
103 uint64_t center_index = 0; // index of center of the largest palindrome
104
105 for (uint64_t i = 1; i < stuffed_string.size() - 1; i++) {
106 if (palindrome_max_half_length[i] > half_length) {
107 half_length = palindrome_max_half_length[i];
108 center_index = i;
109 }
110 }
111
112 std::string palindromic_substring =
113 ""; // contains the resulting largest palindrome
114
115 if (half_length > 0) {
116 // extra information: when '#' is the center, then palindromic
117 // substring will have even length, else palindromic substring will
118 // have odd length
119
120 uint64_t start =
121 center_index - half_length +
122 1; // index of first character of palindromic substring
123 uint64_t end =
124 center_index + half_length -
125 1; // index of last character of palindromic substring
126 for (uint64_t index = start; index <= end; index += 2) {
127 palindromic_substring += stuffed_string[index];
128 }
129 } else {
130 // if length = 0, then there does not exist any palindrome of length
131 // > 1 so we can assign any character of length 1 from string as the
132 // palindromic substring
133 palindromic_substring = prototype[0];
134 }
135 return palindromic_substring;
136
137 } else {
138 // handling case when string is empty
139 return "";
140 }
141}
T end(T... args)
T right(T... args)
T min(T... args)
T size(T... args)
Here is the call graph for this function:

◆ test()

static void test ( )
static

Self-test implementations.

Returns
void
150 {
151 assert(strings::manacher::manacher("") == "");
152 assert(strings::manacher::manacher("abababc") == "ababa");
153 assert(strings::manacher::manacher("cbaabd") == "baab");
154 assert(strings::manacher::manacher("DedzefDeD") == "DeD");
155 assert(strings::manacher::manacher("XZYYXXYZXX") == "YXXY");
156 assert(strings::manacher::manacher("1sm222m10abc") == "m222m");
157 assert(strings::manacher::manacher("798989591") == "98989");
158 assert(strings::manacher::manacher("xacdedcax") == "xacdedcax");
159 assert(strings::manacher::manacher("xaccax") == "xaccax");
160 assert(strings::manacher::manacher("a") == "a");
161 assert(strings::manacher::manacher("xy") == "x");
162 assert(strings::manacher::manacher("abced") == "a");
163
164 std::cout << "All tests have passed!" << std::endl;
165}
T endl(T... args)
Here is the call graph for this function: