A function that implements Manacher's algorithm.
41 {
42 if (prototype.size() > 0) {
43
44
45 std::string stuffed_string = "";
46 for (auto str : prototype) {
47 stuffed_string += str;
48 stuffed_string += "#";
49 }
50 stuffed_string = "@#" + stuffed_string + "&";
51
52 std::vector<uint64_t> palindrome_max_half_length(
53 stuffed_string.size(),
54 0);
55
56
57
58
59 uint64_t bigger_center =
60 0;
61
62
63
64 uint64_t right = 0;
65
66
67
68
69 for (uint64_t i = 1; i < stuffed_string.size() - 1; i++) {
70 if (i < right) {
71
72 uint64_t opposite_to_i =
73 2 * bigger_center -
74 i;
75
76
77
78
79
80
81 palindrome_max_half_length[i] = std::min(
82 palindrome_max_half_length[opposite_to_i], right - i);
83 }
84
85
86
87 while (stuffed_string[i + (palindrome_max_half_length[i] + 1)] ==
88 stuffed_string[i - (palindrome_max_half_length[i] + 1)]) {
89 palindrome_max_half_length[i]++;
90 }
91
92
93
94
95
96 if (i + palindrome_max_half_length[i] > right) {
97 bigger_center = i;
98 right = i + palindrome_max_half_length[i];
99 }
100 }
101
102
103 uint64_t half_length = 0;
104 uint64_t center_index = 0;
105
106 for (uint64_t i = 1; i < stuffed_string.size() - 1; i++) {
107 if (palindrome_max_half_length[i] > half_length) {
108 half_length = palindrome_max_half_length[i];
109 center_index = i;
110 }
111 }
112
113 std::string palindromic_substring =
114 "";
115
116 if (half_length > 0) {
117
118
119
120
121 uint64_t start =
122 center_index - half_length +
123 1;
124 uint64_t end =
125 center_index + half_length -
126 1;
127 for (uint64_t index = start; index <= end; index += 2) {
128 palindromic_substring += stuffed_string[index];
129 }
130 } else {
131
132
133
134 palindromic_substring = prototype[0];
135 }
136 return palindromic_substring;
137
138 } else {
139
140 return "";
141 }
142}
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4