查找给定字符串的所有不同回文子字符串-yiteyi-C++库

给定一个小写ASCII字符字符串，查找其中所有不同的连续回文子字符串。

null

例如：

Input: str = "abaaa"Output:  Below are 5 palindrome sub-stringsaaaaaaababInput: str = "geek"Output:  Below are 4 palindrome sub-stringseeegk

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1：

步骤1：使用改进的Manacher算法查找所有回文： 将每个字符视为轴心，在两侧展开，以找到以所考虑轴心字符为中心的偶数和奇数长度回文的长度，并将长度存储在两个数组中（奇数和偶数）。此步骤的时间复杂度为O（n^2）

第2步：在HashMap中插入所有找到的回文： 将上一步中找到的所有回文插入HashMap。还要将字符串中的所有单个字符插入HashMap（以生成不同的单字母回文子字符串）。假设哈希插入搜索需要O（1）个时间，则此步骤的时间复杂度为O（n^3）。请注意，一个字符串最多可以有O（n^2）个回文子字符串。在C++下面，使用插入和搜索的时间复杂度为O（Logn）的有序哈希映射。在C++中，使用有序哈希映射来实现。红黑树 .

第3步：打印不同回文和不同回文的数量： 最后一步是打印HashMap中存储的所有值（由于HashMap的属性，只有不同的元素会被散列）。映射的大小给出了不同回文连续子字符串的数量。

下面是上述想法的实施。

C++

                         // C++ program to find all distinct palindrome sub-strings                       
                         // of a given string                       
                         #include <iostream>                       
                         #include <map>                       
                         using                                     namespace                                     std;                       
                                   
                         // Function to print all distinct palindrome sub-strings of s                       
                         void                                     palindromeSubStrs(string s)                       
                         {                       
                                                 map<string,                                     int                                     > m;                       
                                                 int                                     n = s.size();                       
                                   
                                                 // table for storing results (2 rows for odd-                       
                                                 // and even-length palindromes                       
                                                 int                                     R[2][n+1];                       
                                   
                                                 // Find all sub-string palindromes from the given input                       
                                                 // string insert 'guards' to iterate easily over s                       
                                                 s =                                     "@"                                     + s +                                     "#"                                     ;                       
                                   
                                                 for                                     (                                     int                                     j = 0; j <= 1; j++)                       
                                                 {                       
                                                 int                                     rp = 0;                                     // length of 'palindrome radius'                       
                                                 R[j][0] = 0;                       
                                   
                                                 int                                     i = 1;                       
                                                 while                                     (i <= n)                       
                                                 {                       
                                                 //  Attempt to expand palindrome centered at i                       
                                                 while                                     (s[i - rp - 1] == s[i + j + rp])                       
                                                 rp++;                                     // Incrementing the length of palindromic                       
                                                 // radius as and when we find vaid palindrome                       
                                   
                                                 // Assigning the found palindromic length to odd/even                       
                                                 // length array                       
                                                 R[j][i] = rp;                       
                                                 int                                     k = 1;                       
                                                 while                                     ((R[j][i - k] != rp - k) && (k < rp))                       
                                                 {                       
                                                 R[j][i + k] = min(R[j][i - k],rp - k);                       
                                                 k++;                       
                                                 }                       
                                                 rp = max(rp - k,0);                       
                                                 i += k;                       
                                                 }                       
                                                 }                       
                                   
                                                 // remove 'guards'                       
                                                 s = s.substr(1, n);                       
                                   
                                                 // Put all obtained palindromes in a hash map to                       
                                                 // find only distinct palindromess                       
                                                 m[string(1, s[0])]=1;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j <= 1; j++)                       
                                                 for                                     (                                     int                                     rp = R[j][i]; rp > 0; rp--)                       
                                                 m[s.substr(i - rp - 1, 2 * rp + j)]=1;                       
                                                 m[string(1, s[i])]=1;                       
                                                 }                       
                                   
                                                 //printing all distinct palindromes from hash map                       
                                                 cout <<                                     "Below are "                                     << m.size()-1                       
                                                 <<                                     " palindrome sub-strings"                                     ;                       
                                                 map<string,                                     int                                     >::iterator ii;                       
                                                 for                                     (ii = m.begin(); ii!=m.end(); ++ii)                       
                                                 cout << (*ii).first << endl;                       
                         }                       
                                   
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 palindromeSubStrs(                                     "abaaa"                                     );                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find all distinct palindrome                       
                         // sub-strings of a given string                       
                         import                                     java.util.Map;                       
                         import                                     java.util.TreeMap;                       
           
                         public                                     class                                     GFG                       
                         {                       
                                                 // Function to print all distinct palindrome                       
                                                 // sub-strings of s                       
                                                 static                                     void                                     palindromeSubStrs(String s)                       
                                                 {                       
                                                 //map<string, int> m;                       
                                                 TreeMap<String , Integer> m =                                     new                                     TreeMap<>();                       
                                                 int                                     n = s.length();                       
                                   
                                                 // table for storing results (2 rows for odd-                       
                                                 // and even-length palindromes                       
                                                 int                                     [][] R =                                     new                                     int                                     [                                     2                                     ][n+                                     1                                     ];                       
                                   
                                                 // Find all sub-string palindromes from the                       
                                                 // given input string insert 'guards' to                       
                                                 // iterate easily over s                       
                                                 s =                                     "@"                                     + s +                                     "#"                                     ;                       
                                   
                                                 for                                     (                                     int                                     j =                                     0                                     ; j <=                                     1                                     ; j++)                       
                                                 {                       
                                                 int                                     rp =                                     0                                     ;                                     // length of 'palindrome radius'                       
                                                 R[j][                                     0                                     ] =                                     0                                     ;                       
                                   
                                                 int                                     i =                                     1                                     ;                       
                                                 while                                     (i <= n)                       
                                                 {                       
                                                 //  Attempt to expand palindrome centered                       
                                                 // at i                       
                                                 while                                     (s.charAt(i - rp -                                     1                                     ) == s.charAt(i +                       
                                                 j + rp))                       
                                                 rp++;                                     // Incrementing the length of                       
                                                 // palindromic radius as and                       
                                                 // when we find valid palindrome                       
                                   
                                                 // Assigning the found palindromic length                       
                                                 // to odd/even length array                       
                                                 R[j][i] = rp;                       
                                                 int                                     k =                                     1                                     ;                       
                                                 while                                     ((R[j][i - k] != rp - k) && (k < rp))                       
                                                 {                       
                                                 R[j][i + k] = Math.min(R[j][i - k],                       
                                                 rp - k);                       
                                                 k++;                       
                                                 }                       
                                                 rp = Math.max(rp - k,                                     0                                     );                       
                                                 i += k;                       
                                                 }                       
                                                 }                       
                                   
                                                 // remove 'guards'                       
                                                 s = s.substring(                                     1                                     , s.length()-                                     1                                     );                       
                                   
                                                 // Put all obtained palindromes in a hash map to                       
                                                 // find only distinct palindromess                       
                                                 m.put(s.substring(                                     0                                     ,                                     1                                     ),                                     1                                     );                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j <=                                     1                                     ; j++)                       
                                                 for                                     (                                     int                                     rp = R[j][i]; rp >                                     0                                     ; rp--)                       
                                                 m.put(s.substring(i - rp -                                     1                                     ,  i - rp -                                     1                       
                                                 +                                     2                                     * rp + j),                                     1                                     );                       
                                                 m.put(s.substring(i, i +                                     1                                     ),                                     1                                     );                       
                                                 }                       
                                   
                                                 // printing all distinct palindromes from                       
                                                 // hash map                       
                                                 System.out.println(                                     "Below are "                                     + (m.size())                       
                                                 +                                     " palindrome sub-strings"                                     );                       
                                   
                                                 for                                     (Map.Entry<String, Integer> ii:m.entrySet())                       
                                                 System.out.println(ii.getKey());                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 palindromeSubStrs(                                     "abaaa"                                     );                       
                                                 }                       
                         }                       
                         // This code is contributed by Sumit Ghosh                       

Python3

                         # Python program Find all distinct palindromic sub-strings                       
                         # of a given string                       
           
                         # Function to print all distinct palindrome sub-strings of s                       
                         def                                     palindromeSubStrs(s):                       
                                                 m                                     =                                     dict                                     ()                       
                                                 n                                     =                                     len                                     (s)                       
           
                                                 # table for storing results (2 rows for odd-                       
                                                 # and even-length palindromes                       
                                                 R                                     =                                     [[                                     0                                     for                                     x                                     in                                     range                                     (n                                     +                                     1                                     )]                                     for                                     x                                     in                                     range                                     (                                     2                                     )]                       
           
                                                 # Find all sub-string palindromes from the given input                       
                                                 # string insert 'guards' to iterate easily over s                       
                                                 s                                     =                                     "@"                                     +                                     s                                     +                                     "#"                       
           
                                                 for                                     j                                     in                                     range                                     (                                     2                                     ):                       
                                                 rp                                     =                                     0                                     # length of 'palindrome radius'                       
                                                 R[j][                                     0                                     ]                                     =                                     0                       
           
                                                 i                                     =                                     1                       
                                                 while                                     i <                                     =                                     n:                       
           
                                                 # Attempt to expand palindrome centered at i                       
                                                 while                                     s[i                                     -                                     rp                                     -                                     1                                     ]                                     =                                     =                                     s[i                                     +                                     j                                     +                                     rp]:                       
                                                 rp                                     +                                     =                                     1                                     # Incrementing the length of palindromic                       
                                                 # radius as and when we find valid palindrome                       
           
                                                 # Assigning the found palindromic length to odd/even                       
                                                 # length array                       
                                                 R[j][i]                                     =                                     rp                       
                                                 k                                     =                                     1                       
                                                 while                                     (R[j][i                                     -                                     k] !                                     =                                     rp                                     -                                     k)                                     and                                     (k < rp):                       
                                                 R[j][i                                     +                                     k]                                     =                                     min                                     (R[j][i                                     -                                     k], rp                                     -                                     k)                       
                                                 k                                     +                                     =                                     1                       
                                                 rp                                     =                                     max                                     (rp                                     -                                     k,                                     0                                     )                       
                                                 i                                     +                                     =                                     k                       
           
                                                 # remove guards                       
                                                 s                                     =                                     s[                                     1                                     :                                     len                                     (s)                                     -                                     1                                     ]                       
           
                                                 # Put all obtained palindromes in a hash map to                       
                                                 # find only distinct palindrome                       
                                                 m[s[                                     0                                     ]]                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n):                       
                                                 for                                     j                                     in                                     range                                     (                                     2                                     ):                       
                                                 for                                     rp                                     in                                     range                                     (R[j][i],                                     0                                     ,                                     -                                     1                                     ):                       
                                                 m[s[i                                     -                                     rp                                     -                                     1                                     : i                                     -                                     rp                                     -                                     1                                     +                                     2                                     *                                     rp                                     +                                     j]]                                     =                                     1                       
                                                 m[s[i]]                                     =                                     1                       
           
                                                 # printing all distinct palindromes from hash map                       
                                                 print                                     (                                     "Below are "                                     +                                     str                                     (                                     len                                     (m))                                     +                                     " pali sub-strings"                                     )                       
                                                 for                                     i                                     in                                     m:                       
                                                 print                                     (i)                       
           
                         # Driver program                       
                         palindromeSubStrs(                                     "abaaa"                                     )                       
                         # This code is contributed by BHAVYA JAIN and ROHIT SIKKA                       

C#

                         // C# program to find all distinct palindrome                       
                         // sub-strings of a given string                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Function to print all distinct palindrome                       
                                                 // sub-strings of s                       
                                                 public                                     static                                     void                                     palindromeSubStrs(                                     string                                     s)                       
                                                 {                       
                                                 //map<string, int> m;                       
                                                 Dictionary <                                     string                                     ,                       
                                                 int                                     > m =                                     new                                     Dictionary <                                     string                                     ,                       
                                                 int                                     > ();                       
                                                 int                                     n = s.Length;                       
           
                                                 // table for storing results (2 rows for odd-                       
                                                 // and even-length palindromes                       
                                                 int                                     [, ] R =                                     new                                     int                                     [2, n + 1];                       
           
                                                 // Find all sub-string palindromes from the                       
                                                 // given input string insert 'guards' to                       
                                                 // iterate easily over s                       
                                                 s =                                     "@"                                     + s +                                     "#"                                     ;                       
                                                 for                                     (                                     int                                     j = 0; j <= 1; j++)                       
                                                 {                       
                                                 int                                     rp = 0;                                     // length of 'palindrome radius'                       
                                                 R[j, 0] = 0;                       
                                                 int                                     i = 1;                       
                                                 while                                     (i <= n)                       
                                                 {                       
                                   
                                                 // Attempt to expand palindrome centered                       
                                                 // at i                       
                                                 while                                     (s[i - rp - 1] == s[i + j + rp])                       
           
                                                 // Incrementing the length of                       
                                                 // palindromic radius as and                       
                                                 // when we find valid palindrome                       
                                                 rp++;                       
           
                                                 // Assigning the found palindromic length                       
                                                 // to odd/even length array                       
                                                 R[j, i] = rp;                       
                                                 int                                     k = 1;                       
                                                 while                                     ((R[j, i - k] != rp - k) && k < rp)                       
                                                 {                       
                                                 R[j, i + k] = Math.Min(R[j, i - k], rp - k);                       
                                                 k++;                       
                                                 }                       
                                                 rp = Math.Max(rp - k, 0);                       
                                                 i += k;                       
                                                 }                       
                                                 }                       
           
                                                 // remove 'guards'                       
                                                 s = s.Substring(1);                       
           
                                                 // Put all obtained palindromes in a hash map to                       
                                                 // find only distinct palindromess                       
                                                 if                                     (!m.ContainsKey(s.Substring(0, 1)))                       
                                                 m.Add(s.Substring(0, 1), 1);                       
                                                 else                       
                                                 m[s.Substring(0, 1)]++;                       
           
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j <= 1; j++)                       
                                                 for                                     (                                     int                                     rp = R[j, i]; rp > 0; rp--)                       
                                                 {                       
                                                 if                                     (!m.ContainsKey(s.Substring(i - rp - 1, 2 * rp + j)))                       
                                                 m.Add(s.Substring(i - rp - 1, 2 * rp + j), 1);                       
                                                 else                       
                                                 m[s.Substring(i - rp - 1, 2 * rp + j)]++;                       
                                                 }                       
           
                                                 if                                     (!m.ContainsKey(s.Substring(i, 1)))                       
                                                 m.Add(s.Substring(i, 1), 1);                       
                                                 else                       
                                                 m[s.Substring(i, 1)]++;                       
                                                 }                       
           
                                                 // printing all distinct palindromes from                       
                                                 // hash map                       
                                                 Console.WriteLine(                                     "Below are "                                     + (m.Count));                       
           
                                                 foreach                                     (KeyValuePair <                                     string                                     ,                                     int                                     > ii                                     in                                     m)                       
                                                 Console.WriteLine(ii.Key);                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                                                 {                       
                                                 palindromeSubStrs(                                     "abaaa"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // sanjeev2552                       

输出：

 Below are 5 palindrome sub-stringsaaaaaaabab

方法2：

字符串长度–N

第一步：找到所有回文子字符串

首先对每个子字符串检查它是否是回文的或没有使用 动态规划 像这样—— https://www.geeksforgeeks.org/count-palindrome-sub-strings-string/

时间复杂性–O（N） ^2. )空间复杂度-O（N） ^2. )

第2步：删除重复的回文

对于从索引0开始的每个索引，我们将使用 国民党 算法，并检查前缀和后缀是否相同且是回文的，然后我们将为该后缀子字符串的dp数组设置0

时间复杂度O（N） ^2. )KMP阵列的空间复杂度O（N）

第三步：打印不同的回文和回文数

对于每个子字符串，检查它是否存在于dp数组中（即dp[i][j]==true），并打印它。

时间复杂度O（N） ^2. )空间复杂度O（N）

总体时间复杂度–O（N） ^2. )

总体空间复杂度–O（N） ^2. )

下面是上述想法的实施。

C++

                         // C++ program to find all distinct palindrome sub-strings                       
                         // of a given string                       
                         #include <iostream>                       
                         #include <vector>                       
                         using                                     namespace                                     std;                       
           
                         int                                     solve(string s)                       
                         {                       
                                                 int                                     n = s.size();                       
                                                 // dp array to store whether a substring is palindrome                       
                                                 // or not using dynamic programming we can solve this                       
                                                 // in O(N^2)                       
                                                 // dp[i][j] will be true (1) if substring (i, j) is                       
                                                 // palindrome else false (0)                       
                                                 vector<vector<                                     bool                                     > > dp(n, vector<                                     bool                                     >(n,                                     false                                     ));                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 // base case every char is palindrome                       
                                                 dp[i][i] = 1;                       
                                                 // check for every substring of length 2                       
                                                 if                                     (i < n && s[i] == s[i + 1]) {                       
                                                 dp[i][i + 1] = 1;                       
                                                 }                       
                                                 }                       
                                                 // check every substring of length greater than 2 for                       
                                                 // palindrome                       
                                                 for                                     (                                     int                                     len = 3; len <= n; len++) {                       
                                                 for                                     (                                     int                                     i = 0; i + len - 1 < n; i++) {                       
                                                 if                                     (s[i] == s[i + (len - 1)]                       
                                                 && dp[i + 1][i + (len - 1) - 1]) {                       
                                                 dp[i][i + (len - 1)] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*                       
                                                 // here we will apply kmp algorithm for substrings                       
                                                 // starting from i = 0 to n-1 when we will find prefix                       
                                                 // and suffix of a substring to be equal and it is                       
                                                 // palindrome we will make dp[i][j] for that suffix to be                       
                                                 // false which means it is already added in the prefix                       
                                                 // and we should not count it anymore.                       
                                                 vector<                                     int                                     > kmp(n, 0);                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 // starting kmp for every i form 0 to n-1                       
                                                 int                                     j = 0, k = 1;                       
                                                 while                                     (k + i < n) {                       
                                                 if                                     (s[j + i] == s[k + i]) {                       
                                                 // make suffix to be false                       
                                                 // if this suffix is palindrome then it is                       
                                                 // already included in in prefix                       
                                                 dp[k + i - j][k + i] =                                     false                                     ;                       
                                                 kmp[k++] = ++j;                       
                                                 }                       
                                                 else                                     if                                     (j > 0) {                       
                                                 j = kmp[j - 1];                       
                                                 }                       
                                                 else                                     {                       
                                                 kmp[k++] = 0;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*                       
                                                 int                                     count = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 string str;                       
                                                 for                                     (                                     int                                     j = i; j < n; j++) {                       
                                                 str += s[j];                       
                                                 if                                     (dp[i][j]) {                       
                                                 // count number of resultant distinct                       
                                                 // substrings and print print that substring                       
                                                 count++;                       
                                                 cout << str <<                                     ''                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 cout <<                                     "Total number of distinct palindromes is "                       
                                                 << count <<                                     ''                                     ;                       
                         }                       
           
                         // Driver code starts                       
                         // This code is contributed by Aditya Anand                       
                         int                                     main()                       
                         {                       
                                                 string s1 =                                     "abaaa"                                     , s2 =                                     "aaaaaaaaaa"                                     ;                       
                                                 solve(s1);                       
                                                 solve(s2);                       
                                                 return                                     0;                       
                         }                       
                         // Driver code ends                       

输出

aababaaaaaTotal number of distinct palindromes is 5aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTotal number of distinct palindromes is 10

类似的问题： 计算一个字符串中的所有回文子字符串本文由维涅什·纳拉亚南和索米亚·桑帕斯。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章