fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of functions based on Manacher's
  6. // algorithm for palindromic substrings. Each function is ready to be
  7. // used as a "black box". Read the comments above each one to understand:
  8. //   - What it solves
  9. //   - What input it expects
  10. //   - What it returns
  11. //   - Time complexity
  12. //   - Important constraints / assumptions
  13. // ===================================================================
  14.  
  15. // ===================================================================
  16. // TERMINOLOGY EXPLANATION:
  17. //   - d1[i] : number of odd-length palindromes with center at index i.
  18. //             It includes the single character itself.
  19. //             The maximum palindrome radius (in characters) is d1[i],
  20. //             and the length of that longest palindrome is 2*d1[i] - 1.
  21. //             For example, d1[i] = 3 means the palindrome of length 5
  22. //             centered at i exists.
  23. //   - d2[i] : number of even-length palindromes centered between
  24. //             index i-1 and index i. (For i from 0 to n-1, we consider
  25. //             the gap before index i.) If d2[i] > 0, there is at least
  26. //             one even palindrome with that center. The maximum radius
  27. //             (in characters) is d2[i], and length is 2*d2[i].
  28. //             Example: d2[2] = 2 means the palindrome of length 4
  29. //             centered between indices 1 and 2 exists.
  30. // ===================================================================
  31.  
  32. // ===================================================================
  33. // 1) Core Manacher algorithm
  34. //    Computes the two radius arrays d1 and d2 for a given string.
  35. // ===================================================================
  36.  
  37. // 1.1) manacher
  38. // ============================================================================
  39. // PURPOSE:
  40. //   Computes the Manacher arrays for the input string. These arrays allow
  41. //   O(1) checks for palindromic substrings and are the basis for all other
  42. //   functions in this file.
  43. //
  44. // INPUT:
  45. //   s : a string (can contain any characters, including spaces if handled).
  46. //
  47. // OUTPUT:
  48. //   Returns a pair of vectors of integers:
  49. //     - first  : d1, size n (n = s.length())
  50. //     - second : d2, size n
  51. //
  52. // TIME COMPLEXITY:
  53. //   O(n) where n = s.length().
  54. //
  55. // CONSTRAINTS / PRECONDITIONS:
  56. //   - The string can be empty (then both vectors are empty).
  57. //   - Works for any character type (char, wchar_t, etc.) as long as
  58. //     equality is defined.
  59. //
  60. // NOTES:
  61. //   - This function is used internally by most other functions.
  62. //   - The arrays d1 and d2 are explained in the terminology section above.
  63. // ============================================================================
  64. pair<vector<int>, vector<int>> manacher(const string& s) {
  65.     int n = (int)s.size();
  66.     vector<int> d1(n), d2(n);
  67.  
  68.     // Odd-length palindromes (d1)
  69.     for (int i = 0, l = 0, r = -1; i < n; i++) {
  70.         int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  71.         while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
  72.             k++;
  73.         }
  74.         d1[i] = k--;
  75.         if (i + k > r) {
  76.             l = i - k;
  77.             r = i + k;
  78.         }
  79.     }
  80.  
  81.     // Even-length palindromes (d2)
  82.     for (int i = 0, l = 0, r = -1; i < n; i++) {
  83.         int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
  84.         while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) {
  85.             k++;
  86.         }
  87.         d2[i] = k--;
  88.         if (i + k > r) {
  89.             l = i - k - 1;
  90.             r = i + k;
  91.         }
  92.     }
  93.  
  94.     return {d1, d2};
  95. }
  96.  
  97. // ===================================================================
  98. // 2) Basic Queries using Manacher arrays
  99. //    These functions rely on precomputed d1 and d2.
  100. // ===================================================================
  101.  
  102. // 2.1) isPalSubstring
  103. // ============================================================================
  104. // PURPOSE:
  105. //   Checks whether the substring s[l..r] (inclusive) is a palindrome.
  106. //
  107. // INPUT:
  108. //   l, r : 0-based indices (l <= r).
  109. //   d1, d2 : Manacher arrays (obtained from manacher(s)).
  110. //
  111. // OUTPUT:
  112. //   Returns true if s[l..r] is a palindrome, false otherwise.
  113. //
  114. // TIME COMPLEXITY:
  115. //   O(1)
  116. //
  117. // CONSTRAINTS / PRECONDITIONS:
  118. //   - l and r must be valid indices (0 <= l <= r < n).
  119. //   - d1 and d2 must correspond to the same string s.
  120. //
  121. // NOTES:
  122. //   - This function does not need the original string, only the Manacher arrays.
  123. //   - For odd length, it checks the required radius at the center.
  124. //   - For even length, it checks the required radius at the gap center.
  125. // ============================================================================
  126. bool isPalSubstring(int l, int r, const vector<int>& d1, const vector<int>& d2) {
  127.     int len = r - l + 1;
  128.     if (len <= 0) return false;
  129.     if (len % 2 == 1) {
  130.         int center = (l + r) / 2;
  131.         int radius = (len + 1) / 2;
  132.         return d1[center] >= radius;
  133.     } else {
  134.         // center is between index c-1 and c, where c = (l+r)/2 + 1
  135.         int center = (l + r) / 2 + 1;
  136.         int radius = len / 2;
  137.         return d2[center] >= radius;
  138.     }
  139. }
  140.  
  141. // ===================================================================
  142. // 3) Longest Palindrome Substring
  143. //    Finds the longest palindromic substring (by length or the actual string).
  144. // ===================================================================
  145.  
  146. // 3.1) longestPalSubstringLength
  147. // ============================================================================
  148. // PURPOSE:
  149. //   Returns the length of the longest palindromic substring of the given string.
  150. //
  151. // INPUT:
  152. //   s : the input string.
  153. //
  154. // OUTPUT:
  155. //   An integer: the maximum length.
  156. //
  157. // TIME COMPLEXITY:
  158. //   O(n) because it calls manacher(s) once.
  159. //
  160. // CONSTRAINTS / PRECONDITIONS:
  161. //   - Works for any string length (including empty, returns 0).
  162. //
  163. // NOTES:
  164. //   - If you also need the substring itself, use longestPalSubstring().
  165. // ============================================================================
  166. int longestPalSubstringLength(const string& s) {
  167.     int n = (int)s.size();
  168.     if (n == 0) return 0;
  169.     auto [d1, d2] = manacher(s);
  170.     int ans = 0;
  171.     for (int i = 0; i < n; i++) {
  172.         ans = max(ans, 2 * d1[i] - 1);
  173.         if (d2[i] > 0) ans = max(ans, 2 * d2[i]);
  174.     }
  175.     return ans;
  176. }
  177.  
  178. // 3.2) longestPalSubstring
  179. // ============================================================================
  180. // PURPOSE:
  181. //   Returns the actual longest palindromic substring itself.
  182. //   If multiple have the same maximum length, the first one (by start index)
  183. //   is returned.
  184. //
  185. // INPUT:
  186. //   s : the input string.
  187. //
  188. // OUTPUT:
  189. //   A string: the longest palindromic substring.
  190. //
  191. // TIME COMPLEXITY:
  192. //   O(n) (manacher + one pass).
  193. //
  194. // CONSTRAINTS / PRECONDITIONS:
  195. //   - If the string is empty, returns an empty string.
  196. //
  197. // NOTES:
  198. //   - The function finds the start index and length of the longest palindrome.
  199. // ============================================================================
  200. string longestPalSubstring(const string& s) {
  201.     int n = (int)s.size();
  202.     if (n == 0) return "";
  203.     auto [d1, d2] = manacher(s);
  204.     int bestLen = 0, bestStart = 0;
  205.  
  206.     for (int i = 0; i < n; i++) {
  207.         // odd length
  208.         int len = 2 * d1[i] - 1;
  209.         if (len > bestLen) {
  210.             bestLen = len;
  211.             bestStart = i - d1[i] + 1;
  212.         }
  213.         // even length
  214.         if (d2[i] > 0) {
  215.             len = 2 * d2[i];
  216.             if (len > bestLen) {
  217.                 bestLen = len;
  218.                 bestStart = i - d2[i];
  219.             }
  220.         }
  221.     }
  222.     return s.substr(bestStart, bestLen);
  223. }
  224.  
  225. // ===================================================================
  226. // 4) Counting Palindromic Substrings
  227. //    Returns the total number of palindromic substrings (including single chars).
  228. // ===================================================================
  229.  
  230. // 4.1) countPalSubstrings
  231. // ============================================================================
  232. // PURPOSE:
  233. //   Counts all palindromic substrings (contiguous) in the given string.
  234. //
  235. // INPUT:
  236. //   s : the input string.
  237. //
  238. // OUTPUT:
  239. //   A long long integer: the total number of palindromic substrings.
  240. //
  241. // TIME COMPLEXITY:
  242. //   O(n) (manacher).
  243. //
  244. // CONSTRAINTS / PRECONDITIONS:
  245. //   - Works for any string; for empty returns 0.
  246. //
  247. // NOTES:
  248. //   - The number can be large (up to n*(n+1)/2), so long long is used.
  249. //   - Single characters are always palindromes.
  250. // ============================================================================
  251. long long countPalSubstrings(const string& s) {
  252.     int n = (int)s.size();
  253.     if (n == 0) return 0;
  254.     auto [d1, d2] = manacher(s);
  255.     long long ans = 0;
  256.     for (int i = 0; i < n; i++) {
  257.         ans += d1[i];          // each d1[i] is number of odd palindromes centered at i
  258.         ans += d2[i];          // each d2[i] is number of even palindromes centered at i
  259.     }
  260.     return ans;
  261. }
  262.  
  263. // 4.2) countOddPalSubstrings
  264. // ============================================================================
  265. // PURPOSE:
  266. //   Counts only the odd-length palindromic substrings.
  267. //
  268. // INPUT:
  269. //   s : input string.
  270. //
  271. // OUTPUT:
  272. //   long long count.
  273. //
  274. // TIME COMPLEXITY:
  275. //   O(n).
  276. //
  277. // NOTES:
  278. //   - Equivalent to sum of d1[i].
  279. // ============================================================================
  280. long long countOddPalSubstrings(const string& s) {
  281.     int n = (int)s.size();
  282.     if (n == 0) return 0;
  283.     auto [d1, d2] = manacher(s);
  284.     long long ans = 0;
  285.     for (int x : d1) ans += x;
  286.     return ans;
  287. }
  288.  
  289. // 4.3) countEvenPalSubstrings
  290. // ============================================================================
  291. // PURPOSE:
  292. //   Counts only the even-length palindromic substrings.
  293. //
  294. // INPUT:
  295. //   s : input string.
  296. //
  297. // OUTPUT:
  298. //   long long count.
  299. //
  300. // TIME COMPLEXITY:
  301. //   O(n).
  302. //
  303. // NOTES:
  304. //   - Equivalent to sum of d2[i].
  305. // ============================================================================
  306. long long countEvenPalSubstrings(const string& s) {
  307.     int n = (int)s.size();
  308.     if (n == 0) return 0;
  309.     auto [d1, d2] = manacher(s);
  310.     long long ans = 0;
  311.     for (int x : d2) ans += x;
  312.     return ans;
  313. }
  314.  
  315. // ===================================================================
  316. // 5) Longest Palindrome Ending at Each Index (and Starting at Each Index)
  317. //    These are useful for problems that split the string into parts.
  318. // ===================================================================
  319.  
  320. // 5.1) longestPalEndingAt
  321. // ============================================================================
  322. // PURPOSE:
  323. //   For each index i, computes the length of the longest palindromic substring
  324. //   that ends at i.
  325. //
  326. // INPUT:
  327. //   s : input string.
  328. //
  329. // OUTPUT:
  330. //   A vector<int> of size n, where res[i] = length of the longest palindrome
  331. //   ending at i. The answer is at least 1 (the character itself).
  332. //
  333. // TIME COMPLEXITY:
  334. //   O(n) (Manacher + O(n) pass with a monotonic deque).
  335. //
  336. // CONSTRAINTS / PRECONDITIONS:
  337. //   - If the string is empty, returns an empty vector.
  338. //
  339. // NOTES:
  340. //   - This is often used when you need to split the string into two palindromes.
  341. //   - The algorithm uses the Manacher radii and a sliding window technique.
  342. //   - The implementation below correctly handles centers with equal right ends.
  343. // ============================================================================
  344. vector<int> longestPalEndingAt(const string& s) {
  345.     int n = (int)s.size();
  346.     if (n == 0) return {};
  347.     auto [d1, d2] = manacher(s);
  348.     vector<int> ends(n, 1); // at least the single character
  349.  
  350.     // ---- Odd palindromes ----
  351.     deque<int> q; // stores indices of centers, with strictly increasing right end
  352.     for (int j = 0; j < n; ++j) {
  353.         int i = j;
  354.         int end = i + d1[i] - 1;
  355.         // Add center only if its right end is strictly greater than the last one.
  356.         // This keeps centers with increasing right ends; the leftmost center always gives the longest length.
  357.         if (q.empty() || end > q.back() + d1[q.back()] - 1) {
  358.             q.push_back(i);
  359.         }
  360.         // Remove centers that can no longer reach position j
  361.         while (!q.empty() && q.front() + d1[q.front()] - 1 < j) {
  362.             q.pop_front();
  363.         }
  364.         if (!q.empty()) {
  365.             int best_i = q.front();
  366.             ends[j] = max(ends[j], 2 * j - 2 * best_i + 1);
  367.         }
  368.     }
  369.  
  370.     // ---- Even palindromes ----
  371.     q.clear();
  372.     for (int j = 0; j < n; ++j) {
  373.         if (d2[j] > 0) {
  374.             int i = j;
  375.             int end = i + d2[i] - 1;
  376.             if (q.empty() || end > q.back() + d2[q.back()] - 1) {
  377.                 q.push_back(i);
  378.             }
  379.         }
  380.         while (!q.empty() && q.front() + d2[q.front()] - 1 < j) {
  381.             q.pop_front();
  382.         }
  383.         if (!q.empty()) {
  384.             int best_i = q.front();
  385.             ends[j] = max(ends[j], 2 * j - 2 * best_i + 2);
  386.         }
  387.     }
  388.  
  389.     return ends;
  390. }
  391.  
  392. // 5.2) longestPalStartingAt
  393. // ============================================================================
  394. // PURPOSE:
  395. //   For each index i, computes the length of the longest palindromic substring
  396. //   that starts at i.
  397. //
  398. // INPUT:
  399. //   s : input string.
  400. //
  401. // OUTPUT:
  402. //   A vector<int> of size n, where res[i] = length of the longest palindrome
  403. //   starting at i.
  404. //
  405. // TIME COMPLEXITY:
  406. //   O(n) (calls longestPalEndingAt on reversed string).
  407. //
  408. // CONSTRAINTS / PRECONDITIONS:
  409. //   - Empty string returns empty vector.
  410. //
  411. // NOTES:
  412. //   - A palindrome starting at i in s corresponds to a palindrome ending at
  413. //     position (n-1-i) in the reversed string. So this function uses that fact.
  414. // ============================================================================
  415. vector<int> longestPalStartingAt(const string& s) {
  416.     int n = (int)s.size();
  417.     if (n == 0) return {};
  418.     string rs = s;
  419.     reverse(rs.begin(), rs.end());
  420.     vector<int> endsRev = longestPalEndingAt(rs);
  421.     vector<int> starts(n);
  422.     for (int i = 0; i < n; ++i) {
  423.         starts[i] = endsRev[n - 1 - i];
  424.     }
  425.     return starts;
  426. }
  427.  
  428. // ===================================================================
  429. // 6) Advanced Trick: Maximum Sum of Two Non-overlapping Palindromes
  430. //    This appeared in ECPC/ACPC problems.
  431. // ===================================================================
  432.  
  433. // 6.1) maxSumTwoPalindromes
  434. // ============================================================================
  435. // PURPOSE:
  436. //   Finds the maximum possible sum of lengths of two non-overlapping
  437. //   palindromic substrings. The two palindromes must not overlap and must
  438. //   be non-empty. They can be adjacent.
  439. //
  440. // INPUT:
  441. //   s : input string.
  442. //
  443. // OUTPUT:
  444. //   An integer: the maximum sum. Returns 0 if no such split possible
  445. //   (e.g., string length < 2).
  446. //
  447. // TIME COMPLEXITY:
  448. //   O(n) (computes ending and starting arrays, then prefix/suffix maxima).
  449. //
  450. // CONSTRAINTS / PRECONDITIONS:
  451. //   - Works for any string; for n<2 returns 0.
  452. //
  453. // NOTES:
  454. //   - The idea: for each split position i (between i and i+1), we take the
  455. //     longest palindrome ending at or before i (prefix) and the longest
  456. //     palindrome starting at i+1 or later (suffix). Their sum is considered.
  457. //     We precompute prefix maxima of ends and suffix maxima of starts.
  458. // ============================================================================
  459. int maxSumTwoPalindromes(const string& s) {
  460.     int n = (int)s.size();
  461.     if (n < 2) return 0;
  462.  
  463.     vector<int> endLen = longestPalEndingAt(s);
  464.     vector<int> startLen = longestPalStartingAt(s);
  465.  
  466.     vector<int> pref(n + 1, 0);
  467.     for (int i = 0; i < n; ++i) {
  468.         pref[i + 1] = max(pref[i], endLen[i]);
  469.     }
  470.  
  471.     vector<int> suff(n + 1, 0);
  472.     for (int i = n - 1; i >= 0; --i) {
  473.         suff[i] = max(suff[i + 1], startLen[i]);
  474.     }
  475.  
  476.     int ans = 0;
  477.     for (int i = 0; i < n - 1; ++i) {
  478.         // first palindrome ends at or before i, second starts at i+1 or later
  479.         ans = max(ans, pref[i + 1] + suff[i + 1]);
  480.     }
  481.     return ans;
  482. }
  483.  
  484. // ===================================================================
  485. // 7) Extra: Quick check if a string can be made palindrome by removing
  486. //    at most one character.
  487. //    A two-pointer solution is simpler and O(n); we implement it here.
  488. // ===================================================================
  489.  
  490. // 7.1) canBePalindromeAfterOneDeletion
  491. // ============================================================================
  492. // PURPOSE:
  493. //   Checks if the string can become a palindrome by deleting at most one
  494. //   character.
  495. //
  496. // INPUT:
  497. //   s : input string.
  498. //
  499. // OUTPUT:
  500. //   Returns true if we can delete at most one character to get a palindrome.
  501. //
  502. // TIME COMPLEXITY:
  503. //   O(n) (two-pointer).
  504. //
  505. // CONSTRAINTS / PRECONDITIONS:
  506. //   - Works for any string; empty string is trivially true.
  507. //
  508. // NOTES:
  509. //   - This function does NOT use Manacher; it uses a simpler two-pointer
  510. //     approach which is more direct for this specific problem.
  511. // ============================================================================
  512. bool canBePalindromeAfterOneDeletion(const string& s) {
  513.     int n = (int)s.size();
  514.     int l = 0, r = n - 1;
  515.     while (l < r && s[l] == s[r]) {
  516.         ++l;
  517.         --r;
  518.     }
  519.     if (l >= r) return true; // already palindrome
  520.  
  521.     // Try deleting s[l] and check if s[l+1..r] is palindrome
  522.     int l1 = l + 1, r1 = r;
  523.     bool ok1 = true;
  524.     while (l1 < r1 && s[l1] == s[r1]) {
  525.         ++l1;
  526.         --r1;
  527.     }
  528.     if (l1 >= r1) return true;
  529.  
  530.     // Try deleting s[r] and check if s[l..r-1] is palindrome
  531.     int l2 = l, r2 = r - 1;
  532.     bool ok2 = true;
  533.     while (l2 < r2 && s[l2] == s[r2]) {
  534.         ++l2;
  535.         --r2;
  536.     }
  537.     if (l2 >= r2) return true;
  538.  
  539.     return false;
  540. }
  541.  
  542. // ===================================================================
  543. // main() – Example usage (you can ignore or modify this part)
  544. // ===================================================================
  545. int main() {
  546.     ios::sync_with_stdio(false);
  547.     cin.tie(nullptr);
  548.  
  549.     string s = "abac";
  550.     cout << "String: " << s << "\n";
  551.  
  552.     // Manacher
  553.     auto [d1, d2] = manacher(s);
  554.     cout << "d1: ";
  555.     for (int x : d1) cout << x << " ";
  556.     cout << "\nd2: ";
  557.     for (int x : d2) cout << x << " ";
  558.     cout << "\n";
  559.  
  560.     // Longest palindrome substring
  561.     cout << "Longest palindrome substring: " << longestPalSubstring(s) << "\n";
  562.     cout << "Length: " << longestPalSubstringLength(s) << "\n";
  563.  
  564.     // Count palindromes
  565.     cout << "Total palindromic substrings: " << countPalSubstrings(s) << "\n";
  566.     cout << "Odd palindromes: " << countOddPalSubstrings(s) << "\n";
  567.     cout << "Even palindromes: " << countEvenPalSubstrings(s) << "\n";
  568.  
  569.     // Check if substring [1,3] is palindrome (s[1..3] = "bac" -> false)
  570.     cout << "Is substring [1,3] palindrome? " << (isPalSubstring(1, 3, d1, d2) ? "Yes" : "No") << "\n";
  571.  
  572.     // Longest palindrome ending at each index
  573.     vector<int> ends = longestPalEndingAt(s);
  574.     cout << "Longest palindrome ending at each index: ";
  575.     for (int x : ends) cout << x << " ";
  576.     cout << "\n";
  577.  
  578.     // Longest palindrome starting at each index
  579.     vector<int> starts = longestPalStartingAt(s);
  580.     cout << "Longest palindrome starting at each index: ";
  581.     for (int x : starts) cout << x << " ";
  582.     cout << "\n";
  583.  
  584.     // Max sum of two non-overlapping palindromes
  585.     cout << "Max sum of two non-overlapping palindromes: " << maxSumTwoPalindromes(s) << "\n";
  586.  
  587.     // Check if can be palindrome after one deletion
  588.     cout << "Can be palindrome after one deletion? " << (canBePalindromeAfterOneDeletion(s) ? "Yes" : "No") << "\n";
  589.  
  590.     return 0;
  591. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
String: abac
d1: 1 2 1 1 
d2: 0 0 0 0 
Longest palindrome substring: aba
Length: 3
Total palindromic substrings: 5
Odd palindromes: 5
Even palindromes: 0
Is substring [1,3] palindrome? No
Longest palindrome ending at each index: 1 1 3 1 
Longest palindrome starting at each index: 3 1 1 1 
Max sum of two non-overlapping palindromes: 4
Can be palindrome after one deletion? Yes
https://ideone.com/P7odre
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!