A function that implements Manacher's algorithm.
40 {
41 if (prototype.
size() > 0) {
42
43
45 for (auto str : prototype) {
46 stuffed_string += str;
47 stuffed_string += "#";
48 }
49 stuffed_string = "@#" + stuffed_string + "&";
50
52 stuffed_string.
size(),
53 0);
54
55
56
57
58 uint64_t bigger_center =
59 0;
60
61
62
64
65
66
67
68 for (uint64_t i = 1; i < stuffed_string.
size() - 1; i++) {
69 if (i < right) {
70
71 uint64_t opposite_to_i =
72 2 * bigger_center -
73 i;
74
75
76
77
78
79
80 palindrome_max_half_length[i] =
std::min(
81 palindrome_max_half_length[opposite_to_i], right - i);
82 }
83
84
85
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
92
93
94
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
102 uint64_t half_length = 0;
103 uint64_t center_index = 0;
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
113 "";
114
115 if (half_length > 0) {
116
117
118
119
120 uint64_t start =
121 center_index - half_length +
122 1;
124 center_index + half_length -
125 1;
126 for (uint64_t index = start; index <=
end; index += 2) {
127 palindromic_substring += stuffed_string[index];
128 }
129 } else {
130
131
132
133 palindromic_substring = prototype[0];
134 }
135 return palindromic_substring;
136
137 } else {
138
139 return "";
140 }
141}