马纳彻算法——线性时间最长回文子串——第4部分

325

在马纳彻算法中 第一部分 和 第二部分 ，我们学习了一些基础知识，了解了LPS长度数组，以及如何根据四种情况有效地计算它。在里面 第三部分 ，我们实现了同样的功能。 在这里，我们将再次回顾这四个案例，并尝试以不同的方式看待它，并实施相同的方法。 这四种情况都取决于当前左侧位置的LPS长度值（L[iMirror]）和（centerRightPosition–currentRightPosition）的值，即（R–i）。这两个信息是已知的，这有助于我们重用以前可用的信息，避免不必要的字符比较。

null

Manacher's Algorithm – Linear Time Longest Palindromic Substring

如果我们看看这四个案例，我们会发现 圣 设置最小值 L[错误] 和 R-i 到 L[i] 然后我们尝试在任何情况下扩展回文。 鉴于人们了解LPS长度数组、位置、索引、对称性等，上述观察可能看起来更直观、更容易理解和实现。

C++

// A C program to implement Manacher’s Algorithm
#include <stdio.h>
#include <string.h>
char text[100];
int min( int a, int b)
{
int res = a;
if (b < a)
res = b;
return res;
}
void findLongestPalindromicString()
{
int N = strlen (text);
if (N == 0)
return ;
N = 2*N + 1; //Position count
int L[N]; //LPS Length Array
L[0] = 0;
L[1] = 1;
int C = 1; //centerPosition
int R = 2; //centerRightPosition
int i = 0; //currentRightPosition
int iMirror; //currentLeftPosition
int maxLPSLength = 0;
int maxLPSCenterPosition = 0;
int start = -1;
int end = -1;
int diff = -1;
//Uncomment it to print LPS Length array
//printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
//get currentLeftPosition iMirror for currentRightPosition i
iMirror = 2*C-i;
L[i] = 0;
diff = R - i;
//If currentRightPosition i is within centerRightPosition R
if (diff > 0)
L[i] = min(L[iMirror], diff);
//Attempt to expand palindrome centered at currentRightPosition i
//Here for odd positions, we compare characters and
//if match then increment LPS Length by ONE
//If even position, we just increment LPS by ONE without
//any character comparison
while ( ((i + L[i]) < N && (i - L[i]) > 0) &&
( ((i + L[i] + 1) % 2 == 0) ||
(text[(i + L[i] + 1)/2] == text[(i - L[i] - 1)/2] )))
{
L[i]++;
}
if (L[i] > maxLPSLength) // Track maxLPSLength
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}
//If palindrome centered at currentRightPosition i
//expand beyond centerRightPosition R,
//adjust centerPosition C based on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//printf("%d ", L[i]);
}
//printf("");
start = (maxLPSCenterPosition - maxLPSLength)/2;
end = start + maxLPSLength - 1;
printf ( "LPS of string is %s : " , text);
for (i=start; i<=end; i++)
printf ( "%c" , text[i]);
printf ( "" );
}
int main( int argc, char *argv[])
{
strcpy (text, "babcbabcbaccba" );
findLongestPalindromicString();
strcpy (text, "abaaba" );
findLongestPalindromicString();
strcpy (text, "abababa" );
findLongestPalindromicString();
strcpy (text, "abcbabcbabcba" );
findLongestPalindromicString();
strcpy (text, "forgeeksskeegfor" );
findLongestPalindromicString();
strcpy (text, "caba" );
findLongestPalindromicString();
strcpy (text, "abacdfgdcaba" );
findLongestPalindromicString();
strcpy (text, "abacdfgdcabba" );
findLongestPalindromicString();
strcpy (text, "abacdedcaba" );
findLongestPalindromicString();
return 0;
} 





               










   JAVA  












                        


        


                                                     


        


                          


        


                                                                                






















                         // Java program to implement Manacher's Algorithm                       


                         import                                     java.util.*;                       


           


                         class                                     GFG                       


                         {                       


                                                 static                                     void                                     findLongestPalindromicString(String text)                       


                                                 {                       


                                                 int                                     N = text.length();                       


                                                 if                                     (N ==                                     0                                     )                       


                                                 return                                     ;                       


                                                 N =                                     2                                     * N +                                     1                                     ;                                     // Position count                       


                                                 int                                     [] L =                                     new                                     int                                     [N +                                     1                                     ];                                     // LPS Length Array                       


                                                 L[                                     0                                     ] =                                     0                                     ;                       


                                                 L[                                     1                                     ] =                                     1                                     ;                       


                                                 int                                     C =                                     1                                     ;                                     // centerPosition                       


                                                 int                                     R =                                     2                                     ;                                     // centerRightPosition                       


                                                 int                                     i =                                     0                                     ;                                     // currentRightPosition                       


                                                 int                                     iMirror;                                     // currentLeftPosition                       


                                                 int                                     maxLPSLength =                                     0                                     ;                       


                                                 int                                     maxLPSCenterPosition =                                     0                                     ;                       


                                                 int                                     start = -                                     1                                     ;                       


                                                 int                                     end = -                                     1                                     ;                       


                                                 int                                     diff = -                                     1                                     ;                       


           


                                                 // Uncomment it to print LPS Length array                       


                                                 // printf("%d %d ", L[0], L[1]);                       


                                                 for                                     (i =                                     2                                     ; i < N; i++)                       


                                                 {                       


           


                                                 // get currentLeftPosition iMirror                       


                                                 // for currentRightPosition i                       


                                                 iMirror =                                     2                                     * C - i;                       


                                                 L[i] =                                     0                                     ;                       


                                                 diff = R - i;                       


           


                                                 // If currentRightPosition i is within                       


                                                 // centerRightPosition R                       


                                                 if                                     (diff >                                     0                                     )                       


                                                 L[i] = Math.min(L[iMirror], diff);                       


           


                                                 // Attempt to expand palindrome centered at                       


                                                 // currentRightPosition i. Here for odd positions,                       


                                                 // we compare characters and if match then                       


                                                 // increment LPS Length by ONE. If even position,                       


                                                 // we just increment LPS by ONE without                       


                                                 // any character comparison                       


                                                 while                                     (((i + L[i]) +                                     1                                     < N && (i - L[i]) >                                     0                                     ) &&                       


                                                 (((i + L[i] +                                     1                                     ) %                                     2                                     ==                                     0                                     ) ||                       


                                                 (text.charAt((i + L[i] +                                     1                                     ) /                                     2                                     ) ==                       


                                                 text.charAt((i - L[i] -                                     1                                     ) /                                     2                                     ))))                       


                                                 {                       


                                                 L[i]++;                       


                                                 }                       


           


                                                 if                                     (L[i] > maxLPSLength)                                     // Track maxLPSLength                       


                                                 {                       


                                                 maxLPSLength = L[i];                       


                                                 maxLPSCenterPosition = i;                       


                                                 }                       


           


                                                 // If palindrome centered at currentRightPosition i                       


                                                 // expand beyond centerRightPosition R,                       


                                                 // adjust centerPosition C based on expanded palindrome.                       


                                                 if                                     (i + L[i] > R)                       


                                                 {                       


                                                 C = i;                       


                                                 R = i + L[i];                       


                                                 }                       


           


                                                 // Uncomment it to print LPS Length array                       


                                                 // printf("%d ", L[i]);                       


                                                 }                       


           


                                                 start = (maxLPSCenterPosition - maxLPSLength) /                                     2                                     ;                       


                                                 end = start + maxLPSLength -                                     1                                     ;                       


                                                 System.out.printf(                                     "LPS of string is %s : "                                     , text);                       


                                                 for                                     (i = start; i <= end; i++)                       


                                                 System.out.print(text.charAt(i));                       


                                                 System.out.println();                       


                                                 }                       


           


                                                 // Driver Code                       


                                                 public                                     static                                     void                                     main(String[] args)                       


                                                 {                       


                                                 String text =                                     "babcbabcbaccba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abaaba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abababa"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abcbabcbabcba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "forgeeksskeegfor"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "caba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abacdfgdcaba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abacdfgdcabba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abacdedcaba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


                                                 }                       


                         }                       


           


                         // This code is contributed by                       


                         // sanjeev2552                       












    






               






               










   Python3  












                        


        


                                                     


        


                          


        


                                                                                






















                         # Python program to implement Manacher's Algorithm                       


                                   


                         def                                     findLongestPalindromicString(text):                       


                                                 N                                     =                                     len                                     (text)                       


                                                 if                                     N                                     =                                     =                                     0                                     :                       


                                                 return                       


                                                 N                                     =                                     2                                     *                                     N                                     +                                     1                                     # Position count                       


                                                 L                                     =                                     [                                     0                                     ]                                     *                                     N                       


                                                 L[                                     0                                     ]                                     =                                     0                       


                                                 L[                                     1                                     ]                                     =                                     1                       


                                                 C                                     =                                     1                                     # centerPosition                       


                                                 R                                     =                                     2                                     # centerRightPosition                       


                                                 i                                     =                                     0                                     # currentRightPosition                       


                                                 iMirror                                     =                                     0                                     # currentLeftPosition                       


                                                 maxLPSLength                                     =                                     0                       


                                                 maxLPSCenterPosition                                     =                                     0                       


                                                 start                                     =                                     -                                     1                       


                                                 end                                     =                                     -                                     1                       


                                                 diff                                     =                                     -                                     1                       


                                   


                                                 # Uncomment it to print LPS Length array                       


                                                 # printf("%d %d ", L[0], L[1]);                       


                                                 for                                     i                                     in                                     range                                     (                                     2                                     ,N):                       


                                   


                                                 # get currentLeftPosition iMirror for currentRightPosition i                       


                                                 iMirror                                     =                                     2                                     *                                     C                                     -                                     i                       


                                                 L[i]                                     =                                     0                       


                                                 diff                                     =                                     R                                     -                                     i                       


                                                 # If currentRightPosition i is within centerRightPosition R                       


                                                 if                                     diff >                                     0                                     :                       


                                                 L[i]                                     =                                     min                                     (L[iMirror], diff)                       


                                   


                                                 # Attempt to expand palindrome centered at currentRightPosition i                       


                                                 # Here for odd positions, we compare characters and                       


                                                 # if match then increment LPS Length by ONE                       


                                                 # If even position, we just increment LPS by ONE without                       


                                                 # any character comparison                       


                                                 try                                     :                       


                                                 while                                     ((i                                     +                                     L[i]) < N                                     and                                     (i                                     -                                     L[i]) >                                     0                                     )                                     and                                               


                                                 (((i                                     +                                     L[i]                                     +                                     1                                     )                                     %                                     2                                     =                                     =                                     0                                     )                                     or                                               


                                                 (text[(i                                     +                                     L[i]                                     +                                     1                                     )                                     /                                     /                                     2                                     ]                                     =                                     =                                     text[(i                                     -                                     L[i]                                     -                                     1                                     )                                     /                                     /                                     2                                     ])):                       


                                                 L[i]                                     +                                     =                                     1                       


                                                 except                                     Exception as e:                       


                                                 pass                       


                                   


                                                 if                                     L[i] > maxLPSLength:                                     # Track maxLPSLength                       


                                                 maxLPSLength                                     =                                     L[i]                       


                                                 maxLPSCenterPosition                                     =                                     i                       


                                   


                                                 # If palindrome centered at currentRightPosition i                       


                                                 # expand beyond centerRightPosition R,                       


                                                 # adjust centerPosition C based on expanded palindrome.                       


                                                 if                                     i                                     +                                     L[i] > R:                       


                                                 C                                     =                                     i                       


                                                 R                                     =                                     i                                     +                                     L[i]                       


                                   


                                                 # Uncomment it to print LPS Length array                       


                                                 # printf("%d ", L[i]);                       


                                                 start                                     =                                     (maxLPSCenterPosition                                     -                                     maxLPSLength)                                     /                                     /                                     2                       


                                                 end                                     =                                     start                                     +                                     maxLPSLength                                     -                                     1                       


                                                 print                                     (                                     "LPS of string is "                                     +                                     text                                     +                                     " : "                                     ,text[start:end                                     +                                     1                                     ])                       


                                   


                         # Driver program                       


                         text1                                     =                                     "babcbabcbaccba"                       


                         findLongestPalindromicString(text1)                       


                                   


                         text2                                     =                                     "abaaba"                       


                         findLongestPalindromicString(text2)                       


                                   


                         text3                                     =                                     "abababa"                       


                         findLongestPalindromicString(text3)                       


                                   


                         text4                                     =                                     "abcbabcbabcba"                       


                         findLongestPalindromicString(text4)                       


                                   


                         text5                                     =                                     "forgeeksskeegfor"                       


                         findLongestPalindromicString(text5)                       


                                   


                         text6                                     =                                     "caba"                       


                         findLongestPalindromicString(text6)                       


                                   


                         text7                                     =                                     "abacdfgdcaba"                       


                         findLongestPalindromicString(text7)                       


                                   


                         text8                                     =                                     "abacdfgdcabba"                       


                         findLongestPalindromicString(text8)                       


                                   


                         text9                                     =                                     "abacdedcaba"                       


                         findLongestPalindromicString(text9)                       


                                   


                         # This code is contributed by BHAVYA JAIN                       












    






               






               










   C#  












                        


        


                                                     


        


                          


        


                                                                                






















                         // C# program to implement Manacher's Algorithm                       


                         using                                     System;                       


           


                         class                                     GFG                       


                         {                       


                                                 static                                     void                                     findLongestPalindromicString(String text)                       


                                                 {                       


                                                 int                                     N = text.Length;                       


                                                 if                                     (N == 0)                       


                                                 return                                     ;                       


                                                 N = 2 * N + 1;                                     // Position count                       


                                                 int                                     [] L =                                     new                                     int                                     [N + 1];                                     // LPS Length Array                       


                                                 L[0] = 0;                       


                                                 L[1] = 1;                       


                                                 int                                     C = 1;                                     // centerPosition                       


                                                 int                                     R = 2;                                     // centerRightPosition                       


                                                 int                                     i = 0;                                     // currentRightPosition                       


                                                 int                                     iMirror;                                     // currentLeftPosition                       


                                                 int                                     maxLPSLength = 0;                       


                                                 int                                     maxLPSCenterPosition = 0;                       


                                                 int                                     start = -1;                       


                                                 int                                     end = -1;                       


                                                 int                                     diff = -1;                       


           


                                                 // Uncomment it to print LPS Length array                       


                                                 // printf("%d %d ", L[0], L[1]);                       


                                                 for                                     (i = 2; i < N; i++)                       


                                                 {                       


           


                                                 // get currentLeftPosition iMirror                       


                                                 // for currentRightPosition i                       


                                                 iMirror = 2 * C - i;                       


                                                 L[i] = 0;                       


                                                 diff = R - i;                       


           


                                                 // If currentRightPosition i is within                       


                                                 // centerRightPosition R                       


                                                 if                                     (diff > 0)                       


                                                 L[i] = Math.Min(L[iMirror], diff);                       


           


                                                 // Attempt to expand palindrome centered at                       


                                                 // currentRightPosition i. Here for odd positions,                       


                                                 // we compare characters and if match then                       


                                                 // increment LPS Length by ONE. If even position,                       


                                                 // we just increment LPS by ONE without                       


                                                 // any character comparison                       


                                                 while                                     (((i + L[i]) + 1 < N && (i - L[i]) > 0) &&                       


                                                 (((i + L[i] + 1) % 2 == 0) ||                       


                                                 (text[(i + L[i] + 1) / 2] ==                       


                                                 text[(i - L[i] - 1) / 2])))                       


                                                 {                       


                                                 L[i]++;                       


                                                 }                       


           


                                                 if                                     (L[i] > maxLPSLength)                                     // Track maxLPSLength                       


                                                 {                       


                                                 maxLPSLength = L[i];                       


                                                 maxLPSCenterPosition = i;                       


                                                 }                       


           


                                                 // If palindrome centered at currentRightPosition i                       


                                                 // expand beyond centerRightPosition R,                       


                                                 // adjust centerPosition C based on expanded palindrome.                       


                                                 if                                     (i + L[i] > R)                       


                                                 {                       


                                                 C = i;                       


                                                 R = i + L[i];                       


                                                 }                       


           


                                                 // Uncomment it to print LPS Length array                       


                                                 // printf("%d ", L[i]);                       


                                                 }                       


           


                                                 start = (maxLPSCenterPosition - maxLPSLength) / 2;                       


                                                 end = start + maxLPSLength - 1;                       


                                                 Console.Write(                                     "LPS of string is {0} : "                                     , text);                       


                                                 for                                     (i = start; i <= end; i++)                       


                                                 Console.Write(text[i]);                       


                                                 Console.WriteLine();                       


                                                 }                       


           


                                                 // Driver Code                       


                                                 public                                     static                                     void                                     Main(String[] args)                       


                                                 {                       


                                                 String text =                                     "babcbabcbaccba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abaaba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abababa"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abcbabcbabcba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "forgeeksskeegfor"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "caba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abacdfgdcaba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abacdfgdcabba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


           


                                                 text =                                     "abacdedcaba"                                     ;                       


                                                 findLongestPalindromicString(text);                       


                                                 }                       


                         }                       


           


                         // This code is contributed by PrinciRaj1992                       












    






               






               










   Javascript  












                        


        


                                                     


        


                          


        


                                                                                






















                         <script>                       


                         // Javascript program to implement Manacher's Algorithm                       


           


                         function                                     findLongestPalindromicString(text)                       


                         {                       


                                                 let N = text.length;                       


                                                 if                                     (N == 0)                       


                                                 return                                     ;                       


                                                 N = 2 * N + 1;                                     // Position count                       


                                                 let L =                                     new                                     Array(N + 1);                                     // LPS Length Array                       


                                                 L[0] = 0;                       


                                                 L[1] = 1;                       


                                                 let C = 1;                                     // centerPosition                       


                                                 let R = 2;                                     // centerRightPosition                       


                                                 let i = 0;                                     // currentRightPosition                       


                                                 let iMirror;                                     // currentLeftPosition                       


                                                 let maxLPSLength = 0;                       


                                                 let maxLPSCenterPosition = 0;                       


                                                 let start = -1;                       


                                                 let end = -1;                       


                                                 let diff = -1;                       


                                   


                                                 // Uncomment it to print LPS Length array                       


                                                 // printf("%d %d ", L[0], L[1]);                       


                                                 for                                     (i = 2; i < N; i++)                       


                                                 {                       


                                   


                                                 // get currentLeftPosition iMirror                       


                                                 // for currentRightPosition i                       


                                                 iMirror = 2 * C - i;                       


                                                 L[i] = 0;                       


                                                 diff = R - i;                       


                                   


                                                 // If currentRightPosition i is within                       


                                                 // centerRightPosition R                       


                                                 if                                     (diff > 0)                       


                                                 L[i] = Math.min(L[iMirror], diff);                       


                                   


                                                 // Attempt to expand palindrome centered at                       


                                                 // currentRightPosition i. Here for odd positions,                       


                                                 // we compare characters and if match then                       


                                                 // increment LPS Length by ONE. If even position,                       


                                                 // we just increment LPS by ONE without                       


                                                 // any character comparison                       


                                                 while                                     (((i + L[i]) + 1 < N && (i - L[i]) > 0) &&                       


                                                 (((i + L[i] + 1) % 2 == 0) ||                       


                                                 (text[Math.floor((i + L[i] + 1) / 2)] ==                       


                                                 text[Math.floor((i - L[i] - 1) / 2)])))                       


                                                 {                       


                                                 L[i]++;                       


                                                 }                       


                                   


                                                 if                                     (L[i] > maxLPSLength)                                     // Track maxLPSLength                       


                                                 {                       


                                                 maxLPSLength = L[i];                       


                                                 maxLPSCenterPosition = i;                       


                                                 }                       


                                   


                                                 // If palindrome centered at currentRightPosition i                       


                                                 // expand beyond centerRightPosition R,                       


                                                 // adjust centerPosition C based on expanded palindrome.                       


                                                 if                                     (i + L[i] > R)                       


                                                 {                       


                                                 C = i;                       


                                                 R = i + L[i];                       


                                                 }                       


                                   


                                                 // Uncomment it to print LPS Length array                       


                                                 // printf("%d ", L[i]);                       


                                                 }                       


                                   


                                                 start = (maxLPSCenterPosition - maxLPSLength) / 2;                       


                                                 end = start + maxLPSLength - 1;                       


                                                 document.write(                                     "LPS of string is "                                     +text+                                     " : "                                     );                       


                                                 for                                     (i = start; i <= end; i++)                       


                                                 document.write(text[i]);                       


                                                 document.write(                                     "<br>"                                     );                       


                         }                       


           


                         // Driver Code                       


           


                         let text =                                     "babcbabcbaccba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "abaaba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "abababa"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "abcbabcbabcba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "forgeeksskeegfor"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "caba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "abacdfgdcaba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "abacdfgdcabba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


                         text =                                     "abacdedcaba"                                     ;                       


                         findLongestPalindromicString(text);                       


           


           


                         // This code is contributed by unknown2108                       


                         </script>                       












    






               






               












  输出： 


LPS of string is babcbabcbaccba : abcbabcbaLPS of string is abaaba : abaabaLPS of string is abababa : abababaLPS of string is abcbabcbabcba : abcbabcbabcbaLPS of string is forgeeksskeegfor : geeksskeegLPS of string is caba : abaLPS of string is abacdfgdcaba : abaLPS of string is abacdfgdcabba : abbaLPS of string is abacdedcaba : abacdedcaba


     其他方法      我们在这里讨论了两种方法。三分之一     第三部分    以及本文中的其他内容。在这两种方法中，我们都使用给定的字符串。在这里，在比较字符进行扩展时，我们必须以不同的方式处理偶数和奇数位置（因为偶数位置不代表字符串中的任何字符）。    为了避免对奇偶位置的不同处理，我们需要使偶数位置也代表一些字符（实际上所有偶数位置都应该代表相同的字符，因为它们在字符比较时必须匹配）。一种方法是通过修改给定字符串或创建给定字符串的新副本，在所有偶数位置设置一些字符。例如，如果输入字符串是“abcb”，那么如果我们在偶数位置添加#作为唯一字符，新字符串应该是“#a#b#c#b#”。    已经讨论过的两种方法可以稍加修改，以便在不需要对奇偶位置进行不同处理的情况下处理修改后的字符串。    我们还可以在字符串的开头和结尾添加两个不同的字符（尚未在字符串中的任何位置使用偶数和奇数位置），作为哨兵，以避免绑定检查。通过这些更改，字符串“abcb”将看起来像“^#a#b#c#b#$”其中^和$是哨兵。    这种实现可能看起来更干净，但需要消耗更多内存。    我们在这里并没有实现这些，因为这是给定实现中的一个简单更改。    本文中讨论的关于修改字符串的方法的实现可以在     最长回文子串第二部分    还有     Java翻译    普林斯顿大学也是如此。    本文由     导演    。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论   


 


                    

        
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
技术文章
    

    
喜欢就支持一下吧
点赞5
        分享

        

            

                
                
CPPKU的头像-yiteyi-C++库

                
            

            
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp line:925的原因-yiteyi-C++库
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp line:925的原因
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp li...
8年前 2.6W+
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案
7年前 9287
Easylogging++入门教程（三）Easylogging++ 配置-yiteyi-C++库
Easylogging++入门教程（三）Easylogging++ 配置
Easylogging++入门教程（三）Easylogging++ 配置
9年前 9056
常见的小波基函数有哪些？如何选择合适的小波基函数？-yiteyi-C++库
常见的小波基函数有哪些？如何选择合适的小波基函数？
常见的小波基函数有哪些？如何选择合适的小波基函数？
8年前 8484
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？-yiteyi-C++库
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？
10年前 6676
Easylogging++入门教程（一）Easylogging++日志库简介-yiteyi-C++库
Easylogging++入门教程（一）Easylogging++日志库简介
Easylogging++入门教程（一）Easylogging++日志库简介
9年前 6608

        

    
    

        
    



            

                
相关推荐

            
ISRO | ISRO CS 2017 |问题6-yiteyi-C++库
ISRO | ISRO CS 2017 |问题6
ISRO | ISRO CS 2017 |问题6
3年前 472
SAP位置编码问题-yiteyi-C++库
SAP位置编码问题
SAP位置编码问题
3年前 287
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）-yiteyi-C++库
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）
3年前 287
STD:：C++中的NExtx置换和Pype置换-yiteyi-C++库
STD:：C++中的NExtx置换和Pype置换
STD:：C++中的NExtx置换和Pype置换
3年前 278
2018年NSIT德里协会黑客团队Geeksforgeks-yiteyi-C++库
2018年NSIT德里协会黑客团队Geeksforgeks
2018年NSIT德里协会黑客团队Geeksforgeks
3年前 278
抗锯齿线|吴小林算法-yiteyi-C++库
抗锯齿线|吴小林算法
抗锯齿线|吴小林算法
3年前 171