fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a complete collection of Palindromic Tree (Eertree)
  6. // algorithms. Each function is ready to be used as a "black box".
  7. //
  8. // READ THIS FIRST:
  9. // A Palindromic Tree (also called Eertree) is a data structure that stores
  10. // all distinct palindromic substrings of a string in O(n) time and memory.
  11. //
  12. // Key concepts you need to understand:
  13. //   - "Palindrome": a string that reads the same forwards and backwards.
  14. //     Example: "racecar", "abba", "a", "aa".
  15. //   - "Palindromic Tree": a tree-like structure where each node represents
  16. //     a distinct palindrome. The tree has two roots:
  17. //       * Root 0: represents the empty string (length -1) - odd length root.
  18. //       * Root 1: represents the imaginary string (length 0) - even length root.
  19. //   - "Suffix link" (or "link"): a pointer from a node to the longest proper
  20. //     palindromic suffix of that node's palindrome.
  21. //   - "len[node]": the length of the palindrome represented by this node.
  22. //   - "occ[node]": how many times this palindrome appears in the string.
  23. //   - "num[node]": how many distinct palindromic suffixes of the palindrome
  24. //     represented by this node.
  25. //   - "diff[node]" and "series link": advanced concepts for efficient DP
  26. //     (explained later).
  27. //
  28. // All functions in this file assume the Palindromic Tree has been built
  29. // by calling addChar() for each character of the input string.
  30. // ===================================================================
  31.  
  32. // ===================================================================
  33. // Class: PalindromicTree
  34. // This class represents a Palindromic Tree (Eertree) for a given string.
  35. // ===================================================================
  36.  
  37. class PalindromicTree {
  38. public:
  39.     // -----------------------------------------------------------------
  40.     // Data members (exposed so you can read results after building)
  41.     // -----------------------------------------------------------------
  42.  
  43.     // next[node][c] = node id of the palindrome formed by adding character c
  44.     // on both sides of the palindrome represented by 'node'.
  45.     // -1 means no such palindrome exists.
  46.     vector<array<int, 26>> next;  // Works for lowercase English letters 'a'..'z'
  47.  
  48.     // len[node] = length of the palindrome represented by this node.
  49.     vector<int> len;
  50.  
  51.     // link[node] = node id of the longest proper palindromic suffix.
  52.     // For root 0 (len=-1), link[0] = 0 (points to itself).
  53.     // For root 1 (len=0), link[1] = 0.
  54.     vector<int> link;
  55.  
  56.     // occ[node] = total number of occurrences of this palindrome
  57.     // in the processed string (after counting with countOccurrences()).
  58.     vector<long long> occ;
  59.  
  60.     // num[node] = number of distinct palindromic suffixes of the palindrome
  61.     // represented by this node (including itself).
  62.     vector<int> num;
  63.  
  64.     // diff[node] = len[node] - len[link[node]].
  65.     // Used for fast DP (series links).
  66.     vector<int> diff;
  67.  
  68.     // seriesLink[node] = the first ancestor (following suffix links)
  69.     // where diff[ancestor] != diff[node].
  70.     // Used for fast DP.
  71.     vector<int> seriesLink;
  72.  
  73.     // The processed string (for debugging / building).
  74.     string s;
  75.  
  76.     // The last node added (longest palindromic suffix of the current string).
  77.     int last;
  78.  
  79.     // Total number of nodes created.
  80.     int sz;
  81.  
  82.     // -----------------------------------------------------------------
  83.     // Constructor: initializes the Palindromic Tree with two roots.
  84.     // -----------------------------------------------------------------
  85.     // PURPOSE:
  86.     //   Creates an empty Palindromic Tree ready to process characters.
  87.     // INPUT:
  88.     //   None.
  89.     // OUTPUT:
  90.     //   A PalindromicTree object initialized with the two roots.
  91.     // TIME COMPLEXITY:
  92.     //   O(1)
  93.     // NOTES:
  94.     //   - Root 0 (index 0): represents the "empty" palindrome of length -1
  95.     //     (used for odd-length palindrome construction).
  96.     //   - Root 1 (index 1): represents the "empty" palindrome of length 0
  97.     //     (used for even-length palindrome construction).
  98.     //   - The tree starts with these two roots only.
  99.     //   - link[0] = 0 (self-loop), link[1] = 0.
  100.     //   - For any character c, next[0][c] and next[1][c] are initialized to -1.
  101.     // ===================================================================
  102.     PalindromicTree() {
  103.         // Initialize next array for the two roots
  104.         next.resize(2);
  105.         for (int i = 0; i < 2; ++i) {
  106.             next[i].fill(-1);
  107.         }
  108.  
  109.         // len[0] = -1 (odd root), len[1] = 0 (even root)
  110.         len = {-1, 0};
  111.  
  112.         // link[0] = 0 (self-loop), link[1] = 0
  113.         link = {0, 0};
  114.  
  115.         // occ, num, diff, seriesLink for the roots
  116.         occ = {0, 0};
  117.         num = {0, 0};
  118.         diff = {0, 0};
  119.         seriesLink = {0, 0};
  120.  
  121.         // last = 1 (the longest palindromic suffix of an empty string is root 1)
  122.         last = 1;
  123.  
  124.         // sz = 2 (two roots)
  125.         sz = 2;
  126.  
  127.         // processed string is empty
  128.         s = "";
  129.     }
  130.  
  131.     // -----------------------------------------------------------------
  132.     // addChar(char c)
  133.     // Adds a new character to the end of the string and updates the tree.
  134.     // -----------------------------------------------------------------
  135.     // PURPOSE:
  136.     //   Processes one new character and updates the Palindromic Tree
  137.     //   to include all palindromic substrings ending at this new position.
  138.     // INPUT:
  139.     //   c: a character (must be in 'a'..'z' for this implementation)
  140.     // OUTPUT:
  141.     //   (void) but updates the internal state of the tree.
  142.     // TIME COMPLEXITY:
  143.     //   O(1) amortized.
  144.     // NOTES:
  145.     //   - This is the core function of the Palindromic Tree.
  146.     //   - After adding all characters, the tree contains all distinct
  147.     //     palindromic substrings of the input string.
  148.     //   - The function handles finding the longest palindromic suffix
  149.     //     and adding a new node if needed.
  150.     //   - It updates 'last' to point to the longest palindromic suffix
  151.     //     of the new string.
  152.     //   - This implementation works for lowercase English letters only.
  153.     //     For other character sets, change the array size and mapping.
  154.     // ===================================================================
  155.     void addChar(char c) {
  156.         int cur = c - 'a';
  157.         s.push_back(c);
  158.         int pos = (int)s.size() - 1;
  159.  
  160.         // Find the largest palindrome that can be extended with c
  161.         // We need a palindrome suffix that has c before it.
  162.         // getLink(last) returns the node that can be extended.
  163.         int curNode = getLink(last);
  164.  
  165.         // If the palindrome already exists, just update its occurrence count
  166.         if (next[curNode][cur] != -1) {
  167.             last = next[curNode][cur];
  168.             occ[last]++;
  169.             return;
  170.         }
  171.  
  172.         // Create a new node for the new palindrome
  173.         int newNode = sz++;
  174.         next.push_back({});
  175.         next[newNode].fill(-1);
  176.         len.push_back(len[curNode] + 2);
  177.         occ.push_back(0);
  178.         num.push_back(0);
  179.         diff.push_back(0);
  180.         seriesLink.push_back(0);
  181.  
  182.         // If the new palindrome has length 1, its suffix link is root 1 (even root)
  183.         if (len[newNode] == 1) {
  184.             link.push_back(1);
  185.         } else {
  186.             // Otherwise, find the longest proper palindromic suffix
  187.             int linkNode = getLink(link[curNode]);
  188.             link.push_back(next[linkNode][cur]);
  189.         }
  190.  
  191.         // Set diff and series link
  192.         diff[newNode] = len[newNode] - len[link[newNode]];
  193.         if (diff[newNode] == diff[link[newNode]]) {
  194.             seriesLink[newNode] = seriesLink[link[newNode]];
  195.         } else {
  196.             seriesLink[newNode] = link[newNode];
  197.         }
  198.  
  199.         // Connect the new node in the tree
  200.         next[curNode][cur] = newNode;
  201.  
  202.         // Update occurrence count for the new node
  203.         occ[newNode] = 1;
  204.  
  205.         // Update num (number of palindromic suffixes)
  206.         num[newNode] = num[link[newNode]] + 1;
  207.  
  208.         // Update last
  209.         last = newNode;
  210.     }
  211.  
  212.     // -----------------------------------------------------------------
  213.     // getLink(int node)
  214.     // Finds the longest palindrome suffix that can be extended.
  215.     // This is an internal helper function.
  216.     // -----------------------------------------------------------------
  217.     // PURPOSE:
  218.     //   Finds the node representing the longest palindromic suffix of
  219.     //   the current string that can be extended with the new character.
  220.     // INPUT:
  221.     //   node: starting node (usually 'last').
  222.     // OUTPUT:
  223.     //   Returns the node id that can be extended.
  224.     // TIME COMPLEXITY:
  225.     //   O(1) amortized.
  226.     // NOTES:
  227.     //   - This is an internal function; you don't normally call it directly.
  228.     //   - It follows suffix links until it finds a palindrome that has
  229.     //     the same character before it as the character being added.
  230.     //   - The condition checks: s[pos - len[node] - 1] == s[pos].
  231.     // ===================================================================
  232.     int getLink(int node) {
  233.         int pos = (int)s.size() - 1;
  234.         while (true) {
  235.             int curLen = len[node];
  236.             if (pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]) {
  237.                 break;
  238.             }
  239.             node = link[node];
  240.         }
  241.         return node;
  242.     }
  243.  
  244.     // -----------------------------------------------------------------
  245.     // build(const string& str)
  246.     // Builds the Palindromic Tree from a whole string.
  247.     // -----------------------------------------------------------------
  248.     // PURPOSE:
  249.     //   Convenience function to build the tree by adding all characters.
  250.     // INPUT:
  251.     //   str: the input string.
  252.     // OUTPUT:
  253.     //   (void) but builds the tree.
  254.     // TIME COMPLEXITY:
  255.     //   O(n) where n = str.size().
  256.     // NOTES:
  257.     //   - This calls addChar() for each character.
  258.     //   - After building, the tree is ready for all queries.
  259.     //   - The string is stored internally as 's'.
  260.     // ===================================================================
  261.     void build(const string& str) {
  262.         for (char c : str) {
  263.             addChar(c);
  264.         }
  265.     }
  266.  
  267.     // -----------------------------------------------------------------
  268.     // countOccurrences()
  269.     // Counts the total occurrences of each palindrome in the string.
  270.     // -----------------------------------------------------------------
  271.     // PURPOSE:
  272.     //   Computes the exact number of times each palindrome appears in the
  273.     //   processed string. This is not just the number of times it was
  274.     //   created as a new palindrome; it also counts occurrences that are
  275.     //   included inside larger palindromes.
  276.     // INPUT:
  277.     //   None.
  278.     // OUTPUT:
  279.     //   Updates the 'occ' array for all nodes.
  280.     // TIME COMPLEXITY:
  281.     //   O(sz) where sz is the number of distinct palindromes.
  282.     // NOTES:
  283.     //   - This is a crucial step. Without calling this function, 'occ'
  284.     //     only counts how many times the palindrome was the *newest*
  285.     //     palindrome added, not its total occurrences.
  286.     //   - The algorithm propagates occurrences from longer palindromes
  287.     //     to their suffix links.
  288.     //   - After calling this, occ[node] = total occurrences of the
  289.     //     palindrome represented by 'node'.
  290.     //   - IMPORTANT: Call this after building the tree and before
  291.     //     using getOccurrences() or any function that needs total counts.
  292.     // ===================================================================
  293.     void countOccurrences() {
  294.         // Process nodes in reverse order of creation
  295.         // (so longer palindromes propagate to shorter suffixes)
  296.         for (int i = sz - 1; i >= 2; --i) {
  297.             occ[link[i]] += occ[i];
  298.         }
  299.     }
  300.  
  301.     // -----------------------------------------------------------------
  302.     // getOccurrences(int node)
  303.     // Returns the total occurrences of a given palindrome.
  304.     // -----------------------------------------------------------------
  305.     // PURPOSE:
  306.     //   Returns how many times the palindrome represented by 'node'
  307.     //   appears in the original string.
  308.     // INPUT:
  309.     //   node: the node id representing a palindrome.
  310.     // OUTPUT:
  311.     //   Returns the total occurrence count as long long.
  312.     // TIME COMPLEXITY:
  313.     //   O(1)
  314.     // NOTES:
  315.     //   - Must call countOccurrences() before using this function.
  316.     //   - If you don't call countOccurrences(), occ[node] may be incomplete.
  317.     //   - To find a node for a specific string, you may need to traverse
  318.     //     the tree (not provided in this simple version).
  319.     // ===================================================================
  320.     long long getOccurrences(int node) const {
  321.         return occ[node];
  322.     }
  323.  
  324.     // -----------------------------------------------------------------
  325.     // getNodeCount()
  326.     // Returns the total number of distinct palindromes in the string.
  327.     // -----------------------------------------------------------------
  328.     // PURPOSE:
  329.     //   Returns the number of distinct palindromic substrings.
  330.     // INPUT:
  331.     //   None.
  332.     // OUTPUT:
  333.     //   Returns the number of nodes minus the two roots.
  334.     // TIME COMPLEXITY:
  335.     //   O(1)
  336.     // NOTES:
  337.     //   - The two roots (0 and 1) are not palindromes in the string.
  338.     //   - So the number of distinct palindromes = sz - 2.
  339.     //   - This is the count of all unique palindromic substrings.
  340.     // ===================================================================
  341.     int getNodeCount() const {
  342.         return sz - 2;
  343.     }
  344.  
  345.     // -----------------------------------------------------------------
  346.     // getNumPalindromicSuffixes(int node)
  347.     // Returns the number of distinct palindromic suffixes of a palindrome.
  348.     // -----------------------------------------------------------------
  349.     // PURPOSE:
  350.     //   Returns how many distinct palindromic suffixes the palindrome
  351.     //   represented by 'node' has (including itself).
  352.     // INPUT:
  353.     //   node: the node id representing a palindrome.
  354.     // OUTPUT:
  355.     //   Returns the count of distinct palindromic suffixes.
  356.     // TIME COMPLEXITY:
  357.     //   O(1)
  358.     // NOTES:
  359.     //   - Example: for "ababa", the palindromic suffixes are:
  360.     //     "ababa", "aba", "a" -> so num = 3.
  361.     //   - This is computed during tree construction.
  362.     // ===================================================================
  363.     int getNumPalindromicSuffixes(int node) const {
  364.         return num[node];
  365.     }
  366.  
  367.     // -----------------------------------------------------------------
  368.     // isPalindromeExists(const string& p)
  369.     // Checks if a given palindrome exists in the tree.
  370.     // -----------------------------------------------------------------
  371.     // PURPOSE:
  372.     //   Returns true if the given palindrome p appears in the string.
  373.     // INPUT:
  374.     //   p: a string to check (must be a palindrome; otherwise returns false).
  375.     // OUTPUT:
  376.     //   Returns true if p is a palindrome and exists in the tree.
  377.     // TIME COMPLEXITY:
  378.     //   O(|p|) (traverses the tree from the center outward).
  379.     // NOTES:
  380.     //   - This function assumes p is a palindrome; if not, it returns false.
  381.     //   - It traverses the tree from the center (odd root for odd length,
  382.     //     even root for even length) using the 'next' transitions.
  383.     //   - Works only for lowercase letters.
  384.     // ===================================================================
  385.     bool isPalindromeExists(const string& p) {
  386.         if (p.empty()) return true;
  387.         int n = (int)p.size();
  388.         // Check if p is a palindrome first.
  389.         for (int i = 0, j = n - 1; i < j; ++i, --j) {
  390.             if (p[i] != p[j]) return false;
  391.         }
  392.         // Determine starting root: odd length -> root 0 (len -1), even -> root 1 (len 0)
  393.         int startRoot = (n % 2 == 0) ? 1 : 0;
  394.         int node = startRoot;
  395.         int mid = n / 2;
  396.         if (n % 2 == 0) {
  397.             // Even length: center is between indices mid-1 and mid.
  398.             // Process characters from center outward (i = mid-1 down to 0)
  399.             for (int i = mid - 1; i >= 0; --i) {
  400.                 int c = p[i] - 'a';
  401.                 if (next[node][c] == -1) return false;
  402.                 node = next[node][c];
  403.             }
  404.         } else {
  405.             // Odd length: center is index mid.
  406.             // Process characters from center down to 0.
  407.             for (int i = mid; i >= 0; --i) {
  408.                 int c = p[i] - 'a';
  409.                 if (next[node][c] == -1) return false;
  410.                 node = next[node][c];
  411.             }
  412.         }
  413.         return true;
  414.     }
  415.  
  416.     // -----------------------------------------------------------------
  417.     // getLPSLength()
  418.     // Returns the length of the longest palindromic substring.
  419.     // -----------------------------------------------------------------
  420.     // PURPOSE:
  421.     //   Returns the length of the longest palindromic substring in the
  422.     //   processed string.
  423.     // INPUT:
  424.     //   None.
  425.     // OUTPUT:
  426.     //   Returns the maximum len[node] for all nodes.
  427.     // TIME COMPLEXITY:
  428.     //   O(sz) where sz is the number of nodes.
  429.     // NOTES:
  430.     //   - The longest palindrome is simply the node with the maximum 'len'.
  431.     //   - This is O(n) in the worst case (number of distinct palindromes).
  432.     //   - The time is proportional to the number of distinct palindromes,
  433.     //     which is O(n).
  434.     // ===================================================================
  435.     int getLPSLength() const {
  436.         int maxLen = 0;
  437.         for (int i = 2; i < sz; ++i) {
  438.             maxLen = max(maxLen, len[i]);
  439.         }
  440.         return maxLen;
  441.     }
  442.  
  443.     // -----------------------------------------------------------------
  444.     // getPalindromicSuffixes(int node)
  445.     // Returns all distinct palindromic suffixes of a given palindrome.
  446.     // -----------------------------------------------------------------
  447.     // PURPOSE:
  448.     //   Returns a vector of all distinct palindromic suffixes of the
  449.     //   palindrome represented by 'node'.
  450.     // INPUT:
  451.     //   node: the node id representing a palindrome.
  452.     // OUTPUT:
  453.     //   Returns a vector of node ids representing the palindromic suffixes.
  454.     // TIME COMPLEXITY:
  455.     //   O(k) where k is the number of palindromic suffixes.
  456.     // NOTES:
  457.     //   - The suffixes are obtained by following the 'link' pointers.
  458.     //   - The list includes the node itself and all its suffix links.
  459.     //   - This is useful for DP problems that need to iterate over
  460.     //     palindromic suffixes.
  461.     //   - The suffixes are in decreasing order of length.
  462.     // ===================================================================
  463.     vector<int> getPalindromicSuffixes(int node) const {
  464.         vector<int> suffixes;
  465.         int cur = node;
  466.         while (cur > 1) {
  467.             suffixes.push_back(cur);
  468.             cur = link[cur];
  469.         }
  470.         return suffixes;
  471.     }
  472.  
  473.     // -----------------------------------------------------------------
  474.     // getPalindromicSuffixesFast(int node)
  475.     // Returns palindromic suffixes using series links (advanced).
  476.     // -----------------------------------------------------------------
  477.     // PURPOSE:
  478.     //   Returns all distinct palindromic suffixes of the palindrome
  479.     //   represented by 'node', but using series links for efficiency.
  480.     //   This is used in DP optimization problems.
  481.     // INPUT:
  482.     //   node: the node id representing a palindrome.
  483.     // OUTPUT:
  484.     //   Returns a vector of node ids representing the palindromic suffixes.
  485.     // TIME COMPLEXITY:
  486.     //   O(k) where k is the number of "series" (groups of equal diff).
  487.     //   This is much faster than following all suffix links in the worst case.
  488.     // NOTES:
  489.     //   - Series links allow skipping multiple suffix links with the same
  490.     //     difference in length.
  491.     //   - This is an advanced concept used for DP problems like:
  492.     //     "Minimum number of palindromes to partition a string".
  493.     //   - Not all problems need this, but it's included for completeness.
  494.     //   - A "series" is a chain of palindromic suffixes where the difference
  495.     //     in length between consecutive palindromes is constant.
  496.     // ===================================================================
  497.     vector<int> getPalindromicSuffixesFast(int node) const {
  498.         vector<int> suffixes;
  499.         int cur = node;
  500.         while (cur > 1) {
  501.             suffixes.push_back(cur);
  502.             // Jump to the next series link
  503.             cur = seriesLink[cur];
  504.         }
  505.         return suffixes;
  506.     }
  507.  
  508.     // -----------------------------------------------------------------
  509.     // getDistinctPalindromes()
  510.     // Returns all distinct palindromic substrings.
  511.     // -----------------------------------------------------------------
  512.     // PURPOSE:
  513.     //   Returns a vector of all distinct palindromic substrings
  514.     //   as strings.
  515.     // INPUT:
  516.     //   None.
  517.     // OUTPUT:
  518.     //   Returns a vector of strings containing all distinct palindromes.
  519.     // TIME COMPLEXITY:
  520.     //   O(total length of all distinct palindromes) in the worst case.
  521.     //   This can be O(n^2) in the worst case (e.g., "aaaaa...").
  522.     // NOTES:
  523.     //   - This function reconstructs the palindromic strings from the tree.
  524.     //   - It traverses the tree from the roots.
  525.     //   - The total length of all distinct palindromes can be O(n^2),
  526.     //     so use this carefully for very long strings.
  527.     //   - The function is recursive; be cautious of recursion depth.
  528.     // ===================================================================
  529.     vector<string> getDistinctPalindromes() const {
  530.         vector<string> result;
  531.         // We'll use a DFS to traverse the tree.
  532.         // Start from roots 0 and 1.
  533.         // For odd length palindromes (start from root 0):
  534.         function<void(int, string)> dfs = [&](int node, string cur) {
  535.             // Add the current palindrome if it's not a root
  536.             if (node >= 2) {
  537.                 result.push_back(cur);
  538.             }
  539.             for (int c = 0; c < 26; ++c) {
  540.                 if (next[node][c] != -1) {
  541.                     // Add the character on both sides
  542.                     string nextStr = string(1, char('a' + c)) + cur + string(1, char('a' + c));
  543.                     dfs(next[node][c], nextStr);
  544.                 }
  545.             }
  546.         };
  547.  
  548.         // Start from root 0 (odd length palindromes)
  549.         for (int c = 0; c < 26; ++c) {
  550.             if (next[0][c] != -1) {
  551.                 string cur = string(1, char('a' + c));
  552.                 result.push_back(cur);
  553.                 // Continue from this node
  554.                 function<void(int, string)> dfsOdd = [&](int node, string curStr) {
  555.                     for (int nc = 0; nc < 26; ++nc) {
  556.                         if (next[node][nc] != -1) {
  557.                             string nextStr = string(1, char('a' + nc)) + curStr + string(1, char('a' + nc));
  558.                             result.push_back(nextStr);
  559.                             dfsOdd(next[node][nc], nextStr);
  560.                         }
  561.                     }
  562.                 };
  563.                 dfsOdd(next[0][c], cur);
  564.             }
  565.         }
  566.  
  567.         // Start from root 1 (even length palindromes)
  568.         for (int c = 0; c < 26; ++c) {
  569.             if (next[1][c] != -1) {
  570.                 string cur = string(1, char('a' + c)) + string(1, char('a' + c));
  571.                 result.push_back(cur);
  572.                 function<void(int, string)> dfsEven = [&](int node, string curStr) {
  573.                     for (int nc = 0; nc < 26; ++nc) {
  574.                         if (next[node][nc] != -1) {
  575.                             string nextStr = string(1, char('a' + nc)) + curStr + string(1, char('a' + nc));
  576.                             result.push_back(nextStr);
  577.                             dfsEven(next[node][nc], nextStr);
  578.                         }
  579.                     }
  580.                 };
  581.                 dfsEven(next[1][c], cur);
  582.             }
  583.         }
  584.  
  585.         return result;
  586.     }
  587.  
  588.     // -----------------------------------------------------------------
  589.     // minPalindromicPartitions()
  590.     // Returns the minimum number of palindromes needed to partition the string.
  591.     // -----------------------------------------------------------------
  592.     // PURPOSE:
  593.     //   Computes the minimum number of palindromic substrings needed to
  594.     //   partition the entire string. (Classic DP problem)
  595.     // INPUT:
  596.     //   None. The string must have been built.
  597.     // OUTPUT:
  598.     //   Returns the minimum number of palindromes in a partition.
  599.     // TIME COMPLEXITY:
  600.     //   O(n log n) or O(n) amortized using series links.
  601.     //   This implementation uses the series link optimization to achieve
  602.     //   O(n log n) in practice.
  603.     // NOTES:
  604.     //   - This is an advanced application of the Palindromic Tree.
  605.     //   - The DP is: dp[i] = min(dp[i], dp[j-1] + 1) for each palindromic
  606.     //     suffix ending at position i.
  607.     //   - Series links are used to skip many suffix links with the same diff.
  608.     //   - This gives O(n log n) time complexity instead of O(n^2).
  609.     //   - Example: "abac" -> "a", "b", "a", "c" -> 4 palindromes.
  610.     //     But "aba", "c" -> 2 palindromes! So the answer is 2.
  611.     //   - This function builds a new tree alongside the DP (so it can be called
  612.     //     on an already built tree, but it will rebuild it). This is fine for
  613.     //     typical usage.
  614.     // ===================================================================
  615.     int minPalindromicPartitions() {
  616.         int n = s.size();
  617.         if (n == 0) return 0;
  618.  
  619.         // dp[i] = minimum palindromes to partition s[0..i]
  620.         vector<int> dp(n + 1, 1e9);
  621.         dp[0] = 0;
  622.  
  623.         // We'll rebuild the tree step by step and maintain DP.
  624.         PalindromicTree pt;
  625.         for (int i = 1; i <= n; ++i) {
  626.             pt.addChar(s[i - 1]);
  627.             int node = pt.last;
  628.  
  629.             // Traverse palindromic suffixes using series links
  630.             int cur = node;
  631.             while (cur > 1) {
  632.                 int lenNode = pt.len[cur];
  633.                 int linkNode = pt.link[cur];
  634.                 dp[i] = min(dp[i], dp[i - lenNode] + 1);
  635.  
  636.                 // Use series link to jump to the next series
  637.                 if (pt.diff[cur] == pt.diff[linkNode]) {
  638.                     cur = pt.seriesLink[cur];
  639.                 } else {
  640.                     cur = linkNode;
  641.                 }
  642.             }
  643.         }
  644.         return dp[n];
  645.     }
  646.  
  647.     // -----------------------------------------------------------------
  648.     // maxPalindromicSubsequenceLength()
  649.     // Returns the length of the longest palindromic subsequence.
  650.     // -----------------------------------------------------------------
  651.     // PURPOSE:
  652.     //   Returns the length of the longest palindromic subsequence
  653.     //   (not necessarily contiguous) in the string.
  654.     // INPUT:
  655.     //   None.
  656.     // OUTPUT:
  657.     //   Returns the length of the longest palindromic subsequence.
  658.     // TIME COMPLEXITY:
  659.     //   O(n^2) using standard DP.
  660.     // NOTES:
  661.     //   - This is NOT a Palindromic Tree specific function.
  662.     //   - It's included here because it's a common palindrome-related problem.
  663.     //   - The Palindromic Tree itself does not solve this directly.
  664.     //   - This is a classic DP problem: lps[i][j] = length of LPS in s[i..j].
  665.     //   - This function uses O(n^2) time and O(n^2) memory.
  666.     //   - For very large strings, consider using Manacher or other algorithms.
  667.     // ===================================================================
  668.     int longestPalindromicSubsequence() const {
  669.         int n = s.size();
  670.         if (n == 0) return 0;
  671.         vector<vector<int>> dp(n, vector<int>(n, 0));
  672.         for (int i = 0; i < n; ++i) dp[i][i] = 1;
  673.         for (int len = 2; len <= n; ++len) {
  674.             for (int i = 0; i + len - 1 < n; ++i) {
  675.                 int j = i + len - 1;
  676.                 if (s[i] == s[j]) {
  677.                     dp[i][j] = dp[i + 1][j - 1] + 2;
  678.                 } else {
  679.                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  680.                 }
  681.             }
  682.         }
  683.         return dp[0][n - 1];
  684.     }
  685. };
  686.  
  687. // ===================================================================
  688. // EXTRA FUNCTIONS (Not part of the class, but useful standalone)
  689. // ===================================================================
  690.  
  691. // -----------------------------------------------------------------
  692. // isPalindrome(string s)
  693. // Checks if a string is a palindrome.
  694. // -----------------------------------------------------------------
  695. // PURPOSE:
  696. //   Returns true if the given string is a palindrome.
  697. // INPUT:
  698. //   s: input string.
  699. // OUTPUT:
  700. //   Returns true if s reads the same forwards and backwards.
  701. // TIME COMPLEXITY:
  702. //   O(|s|)
  703. // NOTES:
  704. //   - A simple two-pointer check.
  705. //   - Works for any string.
  706. // ===================================================================
  707. bool isPalindrome(const string& s) {
  708.     int l = 0, r = (int)s.size() - 1;
  709.     while (l < r) {
  710.         if (s[l++] != s[r--]) return false;
  711.     }
  712.     return true;
  713. }
  714.  
  715. // -----------------------------------------------------------------
  716. // countPalindromicSubstrings(const string& s)
  717. // Counts the total number of palindromic substrings (not necessarily distinct).
  718. // -----------------------------------------------------------------
  719. // PURPOSE:
  720. //   Returns the total number of palindromic substrings in s.
  721. //   This includes duplicates (i.e., counts each occurrence separately).
  722. // INPUT:
  723. //   s: input string.
  724. // OUTPUT:
  725. //   Returns the total count of palindromic substrings.
  726. // TIME COMPLEXITY:
  727. //   O(n^2) using the standard DP or O(n) using Manacher.
  728. // NOTES:
  729. //   - This function uses the standard O(n^2) DP approach.
  730. //   - For O(n) complexity, use Manacher's algorithm.
  731. //   - The Palindromic Tree can also be used to count distinct palindromes.
  732. // ===================================================================
  733. long long countPalindromicSubstrings(const string& s) {
  734.     int n = s.size();
  735.     vector<vector<bool>> dp(n, vector<bool>(n, false));
  736.     long long ans = 0;
  737.     for (int i = 0; i < n; ++i) {
  738.         dp[i][i] = true;
  739.         ans++;
  740.     }
  741.     for (int len = 2; len <= n; ++len) {
  742.         for (int i = 0; i + len - 1 < n; ++i) {
  743.             int j = i + len - 1;
  744.             if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1])) {
  745.                 dp[i][j] = true;
  746.                 ans++;
  747.             }
  748.         }
  749.     }
  750.     return ans;
  751. }
  752.  
  753. // -----------------------------------------------------------------
  754. // countDistinctPalindromicSubstrings(const string& s)
  755. // Counts the number of distinct palindromic substrings using Palindromic Tree.
  756. // -----------------------------------------------------------------
  757. // PURPOSE:
  758. //   Returns the number of distinct palindromic substrings in s.
  759. // INPUT:
  760. //   s: input string.
  761. // OUTPUT:
  762. //   Returns the count of distinct palindromic substrings.
  763. // TIME COMPLEXITY:
  764. //   O(n) where n = s.size().
  765. // NOTES:
  766. //   - This uses the Palindromic Tree.
  767. //   - The answer is simply the number of nodes minus 2.
  768. // ===================================================================
  769. long long countDistinctPalindromicSubstrings(const string& s) {
  770.     PalindromicTree pt;
  771.     pt.build(s);
  772.     return pt.getNodeCount();
  773. }
  774.  
  775. // -----------------------------------------------------------------
  776. // longestPalindromicSubstringManacher(const string& s)
  777. // Finds the longest palindromic substring using Manacher's algorithm.
  778. // -----------------------------------------------------------------
  779. // PURPOSE:
  780. //   Returns the longest palindromic substring of s.
  781. // INPUT:
  782. //   s: input string.
  783. // OUTPUT:
  784. //   Returns the longest palindromic substring as a string.
  785. // TIME COMPLEXITY:
  786. //   O(n)
  787. // NOTES:
  788. //   - Manacher's algorithm is an alternative to the Palindromic Tree.
  789. //   - It finds the longest palindromic substring in O(n) time and O(n) space.
  790. //   - The Palindromic Tree can also find the longest palindrome using getLPSLength(),
  791. //     but it doesn't return the string itself directly.
  792. // ===================================================================
  793. string longestPalindromicSubstringManacher(const string& s) {
  794.     if (s.empty()) return "";
  795.     // Transform the string to insert separators
  796.     string t = "#";
  797.     for (char c : s) {
  798.         t += c;
  799.         t += '#';
  800.     }
  801.     int n = t.size();
  802.     vector<int> p(n, 0);
  803.     int center = 0, right = 0;
  804.     for (int i = 0; i < n; ++i) {
  805.         int mirror = 2 * center - i;
  806.         if (i < right) {
  807.             p[i] = min(right - i, p[mirror]);
  808.         }
  809.         // Expand around center i
  810.         while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) {
  811.             p[i]++;
  812.         }
  813.         if (i + p[i] > right) {
  814.             center = i;
  815.             right = i + p[i];
  816.         }
  817.     }
  818.     // Find the maximum radius
  819.     int maxLen = 0, centerIdx = 0;
  820.     for (int i = 0; i < n; ++i) {
  821.         if (p[i] > maxLen) {
  822.             maxLen = p[i];
  823.             centerIdx = i;
  824.         }
  825.     }
  826.     // Extract the longest palindrome
  827.     int start = (centerIdx - maxLen) / 2;
  828.     return s.substr(start, maxLen);
  829. }
  830.  
  831. // ===================================================================
  832. // main() with example usage
  833. // ===================================================================
  834.  
  835. int main() {
  836.     ios::sync_with_stdio(false);
  837.     cin.tie(nullptr);
  838.  
  839.     // Example 1: Build a Palindromic Tree and count distinct palindromes
  840.     string s = "abacaba";
  841.     PalindromicTree pt;
  842.     pt.build(s);
  843.     pt.countOccurrences();
  844.  
  845.     cout << "String: " << s << "\n";
  846.     cout << "Number of distinct palindromes: " << pt.getNodeCount() << "\n";
  847.     cout << "Length of longest palindrome: " << pt.getLPSLength() << "\n";
  848.  
  849.     // Example 2: Count occurrences of a specific palindrome (by node id)
  850.     // In practice, you need to know the node id. Here we just print all.
  851.     for (int i = 2; i < pt.sz; ++i) {
  852.         cout << "Palindrome node " << i << " occurs " << pt.getOccurrences(i) << " times\n";
  853.     }
  854.  
  855.     // Example 3: Minimum palindromic partitions
  856.     string s2 = "abac";
  857.     PalindromicTree pt2;
  858.     pt2.build(s2);
  859.     cout << "Minimum palindromic partitions of \"" << s2 << "\": " 
  860.          << pt2.minPalindromicPartitions() << "\n";
  861.  
  862.     // Example 4: Count distinct palindromic substrings using standalone function
  863.     cout << "Distinct palindromes in \"" << s << "\": " 
  864.          << countDistinctPalindromicSubstrings(s) << "\n";
  865.  
  866.     // Example 5: Longest palindromic substring using Manacher
  867.     cout << "Longest palindrome in \"" << s << "\": " 
  868.          << longestPalindromicSubstringManacher(s) << "\n";
  869.  
  870.     // Example 6: Count total palindromic substrings (including duplicates)
  871.     cout << "Total palindromic substrings in \"" << s << "\": " 
  872.          << countPalindromicSubstrings(s) << "\n";
  873.  
  874.     return 0;
  875. }
  876.  
  877. // ===================================================================
  878. // SUMMARY OF ADVANCED TRICKS AND PATTERNS FOR ECPC/ACPC
  879. // ===================================================================
  880. // 
  881. // 1. Palindromic Tree Basics:
  882. //    - Use the tree to get all distinct palindromes and their frequencies.
  883. //    - Always call countOccurrences() after building to get correct counts.
  884. // 
  885. // 2. DP with Series Links:
  886. //    - Used for problems like "minimum palindromic partitions" in O(n log n).
  887. //    - The diff and seriesLink arrays are used to skip many suffix links.
  888. //    - Key insight: Palindromic suffixes with the same diff can be grouped.
  889. // 
  890. // 3. Palindromic Tree + DP:
  891. //    - Many problems require DP on palindromic suffixes.
  892. //    - The tree's 'num' array gives the count of palindromic suffixes.
  893. //    - The series link optimization is crucial for O(n log n) DP.
  894. // 
  895. // 4. Counting Occurrences:
  896. //    - After building, propagate counts from longer to shorter palindromes.
  897. //    - This is done by iterating nodes in reverse order of creation.
  898. // 
  899. // 5. Palindromic Substrings vs Subsequences:
  900. //    - Substrings are contiguous; subsequences are not.
  901. //    - Palindromic Tree solves substring problems efficiently.
  902. //    - Longest Palindromic Subsequence requires standard DP (O(n^2)).
  903. // 
  904. // 6. Common ECPC/ACPC Problems:
  905. //    - "Number of distinct palindromic substrings" -> simple getNodeCount().
  906. //    - "Sum of lengths of all palindromic substrings" -> traverse tree and sum len.
  907. //    - "Minimum palindromic partitions" -> DP with series links.
  908. //    - "Maximum number of palindromic substrings with constraints" -> DP + tree.
  909. //    - "Occurrences of all palindromes" -> countOccurrences().
  910. //    - "Longest palindromic substring" -> getLPSLength().
  911. // 
  912. // 7. Important Constraints:
  913. //    - The Palindromic Tree works for any string length n, O(n) time and memory.
  914. //    - The implementation here assumes lowercase English letters ('a'..'z').
  915. //    - For larger alphabets, replace array<int,26> with unordered_map<int,int>.
  916. //    - The number of distinct palindromes is at most n.
  917. // 
  918. // 8. Tricks:
  919. //    - To find the node for a specific palindrome, you can traverse the tree.
  920. //    - The series link optimization is tricky but powerful.
  921. //    - For problems that require building the tree multiple times, reuse the class.
  922. // 
  923. // 9. Terms Explained:
  924. //    - "Palindrome": a string that reads the same forwards and backwards.
  925. //    - "Suffix link": pointer to the longest proper palindromic suffix.
  926. //    - "Series link": pointer to the first ancestor with a different diff.
  927. //    - "diff": len[node] - len[link[node]].
  928. //    - "DP": Dynamic Programming.
  929. //    - "O(n log n)": Time complexity, where n is the string length.
  930. // 
  931. // 10. When to use Palindromic Tree vs Manacher:
  932. //     - Use Palindromic Tree when you need: distinct palindromes, frequencies,
  933. //       DP on palindromic suffixes, or any advanced palindrome-related query.
  934. //     - Use Manacher when you only need the longest palindromic substring.
  935. //     - Manacher is simpler and faster for that specific task.
  936. // ===================================================================
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
String: abacaba
Number of distinct palindromes: 7
Length of longest palindrome: 7
Palindrome node 2 occurs 4 times
Palindrome node 3 occurs 2 times
Palindrome node 4 occurs 2 times
Palindrome node 5 occurs 1 times
Palindrome node 6 occurs 1 times
Palindrome node 7 occurs 1 times
Palindrome node 8 occurs 1 times
Minimum palindromic partitions of "abac": 2
Distinct palindromes in "abacaba": 7
Longest palindrome in "abacaba": abacaba
Total palindromic substrings in "abacaba": 12
https://ideone.com/Sm0p8W
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!