使字符串回文化所需的最小追加数-yiteyi-C++库

给定一个字符串s，我们需要告诉最少要追加的字符（在末尾插入），以使字符串具有回文性。

null

例如：

Input : s = "abede"Output : 2We can make string palindrome as "abedeba"by adding ba at the end of the string.Input : s = "aabb"Output : 2We can make string palindrome as"aabbaa"by adding aa at the end of the string.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

解决方法是逐个删除字符串开头的字符，并检查字符串是否为回文。例如，考虑上面的字符串，s= “阿贝德” . 我们检查字符串是否为回文。结果为false，然后我们从字符串的开头删除字符，现在字符串变为 “贝德” . 我们检查字符串是否为回文。结果再次为false，然后我们从字符串的开头删除字符，现在字符串变为false “爱德” . 我们检查字符串是否为回文。结果为true，因此输出变为2，即从字符串中删除的字符数。

C++

                         // C program to find minimum number of appends                       
                         // needed to make a string Palindrome                       
                         #include<stdio.h>                       
                         #include<string.h>                       
                         #include<stdbool.h>                       
           
                         // Checking if the string is palindrome or not                       
                         bool                                     isPalindrome(                                     char                                     *str)                       
                         {                       
                                                 int                                     len =                                     strlen                                     (str);                       
           
                                                 // single character is always palindrome                       
                                                 if                                     (len == 1)                       
                                                 return                                     true                                     ;                       
           
                                                 // pointing to first character                       
                                                 char                                     *ptr1 = str;                       
           
                                                 // pointing to last character                       
                                                 char                                     *ptr2 = str+len-1;                       
           
                                                 while                                     (ptr2 > ptr1)                       
                                                 {                       
                                                 if                                     (*ptr1 != *ptr2)                       
                                                 return                                     false                                     ;                       
                                                 ptr1++;                       
                                                 ptr2--;                       
                                                 }                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Recursive function to count number of appends                       
                         int                                     noOfAppends(                                     char                                     s[])                       
                         {                       
                                                 if                                     (isPalindrome(s))                       
                                                 return                                     0;                       
           
                                                 // Removing first character of string by                       
                                                 // incrementing base address pointer.                       
                                                 s++;                       
           
                                                 return                                     1 + noOfAppends(s);                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 char                                     s[] =                                     "abede"                                     ;                       
                                                 printf                                     (                                     "%d"                                     , noOfAppends(s));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum number of appends                       
                         // needed to make a string Palindrome                       
                         class                                     GFG                       
                         {                       
           
                         // Checking if the string is palindrome or not                       
                         static                                     boolean                                     isPalindrome(                                     char                                     []str)                       
                         {                       
                                                 int                                     len = str.length;                       
                                   
                                                 // single character is always palindrome                       
                                                 if                                     (len ==                                     1                                     )                       
                                                 return                                     true                                     ;                       
                                   
                                                 // pointing to first character                       
                                                 int                                     ptr1 =                                     0                                     ;                       
                                   
                                                 // pointing to last character                       
                                                 int                                     ptr2 = len-                                     1                                     ;                       
                                   
                                                 while                                     (ptr2 >= ptr1)                       
                                                 {                       
                                                 if                                     (str[ptr1] != str[ptr2])                       
                                                 return                                     false                                     ;                       
                                                 ptr1++;                       
                                                 ptr2--;                       
                                                 }                       
                                   
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Recursive function to count number of appends                       
                         static                                     int                                     noOfAppends(String s)                       
                         {                       
                                                 if                                     (isPalindrome(s.toCharArray()))                       
                                                 return                                     0                                     ;                       
           
                                                 // Removing first character of string by                       
                                                 // incrementing base address pointer.                       
                                                 s=s.substring(                                     1                                     );                       
           
                                                 return                                     1                                     + noOfAppends(s);                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String arr[])                       
                         {                       
                                                 String s =                                     "abede"                                     ;                       
                                                 System.out.printf(                                     "%d"                                     , noOfAppends(s));                       
                         }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Python3

                         # Python3 program to find minimum number of appends                       
                         # needed to make a String Palindrome                       
           
                         # Checking if the String is palindrome or not                       
                         def                                     isPalindrome(                                     Str                                     ):                       
           
                                                 Len                                     =                                     len                                     (                                     Str                                     )                       
           
                                                 # single character is always palindrome                       
                                                 if                                     (                                     Len                                     =                                     =                                     1                                     ):                       
                                                 return                                     True                       
           
                                                 # pointing to first character                       
                                                 ptr1                                     =                                     0                       
           
                                                 # pointing to last character                       
                                                 ptr2                                     =                                     Len                                     -                                     1                       
           
                                                 while                                     (ptr2 > ptr1):                       
           
                                                 if                                     (                                     Str                                     [ptr1] !                                     =                                     Str                                     [ptr2]):                       
                                                 return                                     False                       
                                                 ptr1                                     +                                     =                                     1                       
                                                 ptr2                                     -                                     =                                     1                       
           
                                                 return                                     True                       
           
                         # Recursive function to count number of appends                       
                         def                                     noOfAppends(s):                       
           
                                                 if                                     (isPalindrome(s)):                       
                                                 return                                     0                       
           
                                                 # Removing first character of String by                       
                                                 # incrementing base address pointer.                       
                                                 del                                     s[                                     0                                     ]                       
           
                                                 return                                     1                                     +                                     noOfAppends(s)                       
           
                         # Driver Code                       
                         se                                     =                                     "abede"                       
                         s                                     =                                     [i                                     for                                     i                                     in                                     se]                       
                         print                                     (noOfAppends(s))                       
           
                         # This code is contributed by Mohit Kumar                       

C#

                         // C# program to find minimum number of appends                       
                         // needed to make a string Palindrome                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Checking if the string is palindrome or not                       
                         static                                     Boolean isPalindrome(                                     char                                     []str)                       
                         {                       
                                                 int                                     len = str.Length;                       
           
                                                 // single character is always palindrome                       
                                                 if                                     (len == 1)                       
                                                 return                                     true                                     ;                       
           
                                                 // pointing to first character                       
                                                 char                                     ptr1 = str[0];                       
           
                                                 // pointing to last character                       
                                                 char                                     ptr2 = str[len-1];                       
           
                                                 while                                     (ptr2 > ptr1)                       
                                                 {                       
                                                 if                                     (ptr1 != ptr2)                       
                                                 return                                     false                                     ;                       
                                                 ptr1++;                       
                                                 ptr2--;                       
                                                 }                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Recursive function to count number of appends                       
                         static                                     int                                     noOfAppends(String s)                       
                         {                       
                                                 if                                     (isPalindrome(s.ToCharArray()))                       
                                                 return                                     0;                       
           
                                                 // Removing first character of string by                       
                                                 // incrementing base address pointer.                       
                                                 s=s.Substring(1);                       
           
                                                 return                                     1 + noOfAppends(s);                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String []arr)                       
                         {                       
                                                 String s =                                     "abede"                                     ;                       
                                                 Console.Write(                                     "{0}"                                     , noOfAppends(s));                       
                         }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       

Javascript

                         <script>                       
                         // Javascript program to find minimum number of appends                       
                         // needed to make a string Palindrome                       
                                   
                                                 // Checking if the string is palindrome or not                       
                                                 function                                     isPalindrome(str)                       
                                                 {                       
                                                 let len = str.length;                       
                                   
                                                 // single character is always palindrome                       
                                                 if                                     (len == 1)                       
                                                 return                                     true                                     ;                       
                                   
                                                 // pointing to first character                       
                                                 let ptr1 = 0;                       
                                   
                                                 // pointing to last character                       
                                                 let  ptr2 = len-1;                       
                                   
                                                 while                                     (ptr2 >= ptr1)                       
                                                 {                       
                                                 if                                     (str[ptr1] != str[ptr2])                       
                                                 return                                     false                                     ;                       
                                                 ptr1++;                       
                                                 ptr2--;                       
                                                 }                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 // Recursive function to count number of appends                       
                                                 function                                     noOfAppends(s)                       
                                                 {                       
                                                 if                                     (isPalindrome(s.split(                                     ""                                     )))                       
                                                 return                                     0;                       
                                   
                                                 // Removing first character of string by                       
                                                 // incrementing base address pointer.                       
                                                 s=s.substring(1);                       
                                   
                                                 return                                     1 + noOfAppends(s);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let s =                                     "abede"                                     ;                       
                                                 document.write(noOfAppends(s));                       
                                   
                         // This code is contributed by unknown2108                       
                         </script>                       

输出

描述了上述方法和O（n**2）方法。

有效方法：

我们也有一个算法，利用 Knuth-Morris-Pratt算法这就是O（n）时间复杂度。

该方法背后的基本思想是，我们计算从末尾算起的最大子字符串，字符串的长度减去该值就是最小的附加数。逻辑是直观的，我们不需要附加回文，只需要那些不构成回文的。为了从末尾找到这个最大的回文，我们反转字符串，计算DFA，然后再次反转字符串（从而获得原始字符串），并找到最终状态，它表示字符串与受尊敬的字符串的匹配数，因此我们在O（n）时间内得到从末尾返回的最大子字符串。

以下是上述方法的实施情况：

C++

                         // CPP program for above approach                       
                         #include <algorithm>                       
                         #include <iostream>                       
                         #include <string>                       
                         using                                     namespace                                     std;                       
           
                         // This class builds the dfa and                       
                         // precomputes the state.                       
                         // See KMP algorithm for explanation                       
                         class                                     kmp_numeric {                       
                         private                                     :                       
                                                 int                                     n;                       
                                                 int                                     ** dfa;                       
           
                         public                                     :                       
                                                 kmp_numeric(string& s)                       
                                                 {                       
                                                 n = s.length();                       
                                                 int                                     c = 256;                       
           
                                                 // Create dfa                       
                                                 dfa =                                     new                                     int                                     *[n];                       
           
                                                 // Iterate from 0 to n                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 dfa[i] =                                     new                                     int                                     ;                       
           
                                                 int                                     x = 0;                       
           
                                                 // Iterate from 0 to n                       
                                                 for                                     (                                     int                                     i = 0; i < c; i++)                       
                                                 dfa[0][i] = 0;                       
           
                                                 // Initialise dfa[0][s[0]] = 1                       
                                                 dfa[0][s[0]] = 1;                       
           
                                                 // Iterate i from 1 to n-1                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++) {                       
           
                                                 // Iterate j from 0 to c - 1                       
                                                 for                                     (                                     int                                     j = 0; j < c; j++) {                       
                                                 dfa[i][j] = dfa[x][j];                       
                                                 }                       
           
                                                 dfa[i][s[i]] = i + 1;                       
                                                 x = dfa[x][s[i]];                       
                                                 }                       
                                                 }                       
           
                                                 // This function finds the overlap                       
                                                 // between two strings,by                       
                                                 // changing the state.                       
                                                 int                                     longest_overlap(string& query)                       
                                                 {                       
           
                                                 // q1 is length of query                       
                                                 int                                     ql = query.length();                       
                                                 int                                     state = 0;                       
           
                                                 // Iterate from 0 to q1 - 1                       
                                                 for                                     (                                     int                                     i = 0; i < ql; i++) {                       
                                                 state = dfa[state][query[i]];                       
                                                 }                       
                                                 return                                     state;                       
                                                 }                       
                         };                       
           
                         int                                     min_appends(string& s)                       
                         {                       
           
                                                 // Reverse the string.                       
                                                 reverse(s.begin(), s.end());                       
           
                                                 // Build the DFA for the                       
                                                 // reversed String                       
                                                 kmp_numeric kmp = s;                       
           
                                                 // Get the original string back                       
                                                 reverse(s.begin(), s.end());                       
           
                                                 // Largest overlap in this case is the                       
                                                 // largest string from the end which                       
                                                 // is a palindrome.                       
                                                 int                                     ans = s.length() - kmp.longest_overlap(s);                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "deep"                                     ;                       
                                                 // Answer : 3                       
           
                                                 string t =                                     "sososososos"                                     ;                       
                                                 // Answer : 0                       
           
                                                 cout << min_appends(s) << endl;                       
                                                 cout << min_appends(t) << endl;                       
                         }                       

输出

建议人： 普拉蒂克·普里亚达桑

相关文章： 动态规划|集28（形成回文的最小插入次数）本文由 舒巴姆·乔杜里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章