The book picks up where the previous one left off, and we continue today by talking about the horse-drawn cart solution to the longest palindrome substring.
Topic: given a string s, find the longest palindrome substring in s.
01Optimization of the centroid extension method - merging parity processing
As the saying goes, there is no best but better, looking at the O(n^2) time complexity, think about it there should be a better program, the answer is yes, horse-drawn cart method can be done in time and space complexity are O(n).
In fact, no matter what algorithms are created to solve a certain problem, so we are still step-by-step to optimize the central expansion method to eventually get the horse-drawn cart method.
We know that there is a very obvious problem in the center expansion method: the length parity of the echo string needs different processing, and we do not know whether the echo string is odd or even before the calculation, resulting in each time we need to simultaneously find out the echo string of the two cases of parity and take the largest one, so we need to first solve the problem of parity caused by the differentiation of the processing.
If we want to solve this problem, we may have to do it in two ways: one, externally, to find a formula to unify parity, and the other, internally, to modify itself to make it uniform.
Regarding the first point, since this question is characterized by different treatments based on parity, and the unity formula is more biased towards the fact that a value can be odd or even to end up with a unity result, for example, for 7 and 8, (7-1)/2 = 3 and (8-1)/2 = 3, the first point is not suitable for this question.
Regarding the second point, there are an even number of spaces between the odd number of characters, and an odd number of spaces between the even number of characters, and odd plus even is still odd, that is, if we take these spaces into account, the parity will be unified, then there is also an analysis of whether the introduction of this space will have an impact on the characteristics of the original palindrome string, in fact, there is no impact, for the odd string is equivalent to the center of the elements on each side of an additional space is still symmetric, for the even number is equivalent to the center of the two elements between the addition of a space between the results are also still symmetric, because the space is more special, we choose a special symbol such as [#], so this program has a feasible.
There is one last small problem with this scheme, and that is how to calculate the echo string length, i.e., to realize that the actual character length is calculated from the processed string.
For example, in the figure above, the original odd echo string length is 5, the length of the processed length is 11, the original even echo string length is 6, out of 13, if we do not take into account the center element i, the actual length of the echo string is exactly equal to half of the processed, that is, the length of the original echo string = (the length of the processed echo string - 1)/2, we will first give a name to this value to facilitate the exchange of the later, called the echo string radius.
Here the optimization scheme is to determine the solution to the parity problem, to solve the string processing after the conversion problem, the following we look at the specific implementation of the code.
//Center Expand - Merge Odd Even
public static string CenterExpandMergeOddEven(string s)
{
//If the string is null or has only one character, return the string directly
if (s == null || < 1)
{
return "";
}
// Preprocess the string, inserting the # character to unify the parity return string
// e.g. s="cabac" is converted to s="#c#a#b#a#c#"
var tmp = $"#{("#", ())}#";
// Record the start position and maximum length of the longest palindrome substring
var startIndex = 0;
var maxLength = 0;
// Iterate through the processed string from left to right, finding the radius of the palindrome for each character
for (var i = 0; i < ; ++i)
{
// Calculate the radius of the current palindrome centered on i
var radius = PalindromicRadius(tmp, i, i);
// If the currently calculated radius is greater than maxLength, update startIndex
if (radius > maxLength)
{
startIndex = (i - radius) / 2;
maxLength = radius.
}
}
// Return from the original string based on startIndex and maxLength.
return (startIndex, maxLength); }// Return from the original string based on startIndex and maxLength.
}
//Radius of the palindromic string
public static int PalindromicRadius(string s, int leftIndex, int rightIndex)
{
// leftIndex is greater than or equal to the first character, rightIndex is less than or equal to the last character, and left and right characters are equal
while (leftIndex >= 0 && rightIndex < && s[leftIndex] == s[rightIndex])
{
//expand one bit from the center to each end
//expand to the left
--leftIndex;
//expand to the right
++rightIndex;
}
//Returns the radius of the echo string (note that it should have been (rightIndex - leftIndex + 1)/2, //but after the condition was met leftIndex and rightIndex were extended to the left and right respectively.
//But after the condition is satisfied, leftIndex and rightIndex are expanded by one to the left and one to the right, respectively.
// Therefore, you need to subtract these two, because the center element is not returned in the calculation also need to subtract one.
//so (rightIndex - leftIndex + 1 - 2 - 1) / 2
// so the final formula is (rightIndex - leftIndex - 1)/2)
return (rightIndex - leftIndex - 2) / 2;
}
time complexity：O(n2), which is O(n) since each traversal to a character requires probing to the left/right2)。
Space complexity: o(1).
Therefore this optimization does not have any performance improvement, only the processing method is optimized, this step is not for nothing, but for the following horse-drawn cart method to do the pre-preparation.
02Re-optimization of the central extension method (horse-drawn cart method)
In the optimization of Re-violent Cracking Method we used the classic practice of trading space for time by storing the results of the already computed substrings to reduce unnecessary computations, in the same way I can use similar ideas to optimize the central expansion method.
Violently decrypted method uses the symmetry of the echo string from the outside to the inside to determine whether it is an echo string, the center of the extension method uses the symmetry of the echo string from the inside to the outside to determine whether it is an echo string, and these two methods are applied to the symmetry to calculate, so can we directly use the symmetry of the echo string to directly determine whether it is an echo string? The answer is yes, we use the following illustration to illustrate the principle.
In the above merge parity processing, we know that after processing the length of the radius of the echo string is our final echo string length. If we store the calculated radius of the echo string, we can use it directly when we need it later.
As shown in the figure above, in the echo string radius line, the green background indicates that the characters have been calculated after the echo string radius, and the center of the expansion is calculated from left to right, at this time after the calculation of s [9] that is, the character c at, then we imagine how to calculate at this time indexed as 10 that is, s [10] elements of the echo string radius it? s [11], s [12] it?
Recalling the symmetry mentioned above, if we take the current position s[9] as the center point, then its right radius and its left radius are symmetric, which means that the corresponding elements should be of the same nature, and it can be reasonably guessed that the radius of s[10] should be the same as the radius of the palindrome of s[8] is also 0. Similarly, it is guessed that s[11] = s[7] = 1 and s[12] = s[6] = 2.
Of course this is not absolute, we just want to bring to illustrate that we can use the symmetry, the symmetry point has been calculated on the use of the results, although the above s [10], s [11], s [12] three values are right, but the description is not accurate, because there is a case of s [10] & gt; s [8]. The figure below:
As shown in the figure above, when the last processing s[7], the radius of the echo string can be obtained as 3, at this time to start calculating s[8], the use of symmetry can be obtained as s[8]>=s[6], therefore, we do not need to calculate the s[8] as the center of the two sides of the expansion of the search for the echo string to s[8] as a starting point, but according to the s[6]=2, we jump directly to the 2-bit, the left from the s[6], right from the s[10], start to expand to both sides to find the actual echo string length centered on s[8], and finally calculated that may be 4, this step is the core of the entire algorithm. s[10], start to both sides of the expansion to find s[8] as the center of the actual length of the echo string, the final calculation may be 4, this step is the core of the entire algorithm.
Thus we can divide this algorithm into two cases:
(1) If the current position is greater than the farthest position to the right of the current detected position, then the center expansion method is used directly to find the echo string;
(2) The current position is less than or equal to the farthest position on the right side of the current detection, then according to its symmetric position has been calculated, the direct choice to skip part of the bit and then begin to use the center of the expansion method to find the echo string;
Of course, the starting position, has been detected the rightmost position, the center point, the maximum length of how to choose, when to update, skip how many bits before calculating, these are the details of the part, we look directly at the code below.
//Horse-drawn cart method
public static string Manacher(string s)
{
if (s == null || == 0)
return ""; {
return "";
}
var tmp = $"#{("#", ())}#";
// rightIndex represents the rightmost range calculated so far, rightIndex and left are both detected
var rightIndex = 0;
//centerIndex rightmost position of the center symmetry point
var centerIndex = 0;
// Record the start position and maximum length of the longest echo substring
var startIndex = 0;
var maxLength = 0;
//radiusPoints array records all the radius of the detected echo strings, when we calculate i later, we calculate i according to radiusPoints[iMirror].
var radiusPoints = new int[]; //Iterate through the array from left to right.
// Iterate through the processed string from left to right and find the radius of the palindrome for each character.
for (var i = 0; i < ; i++)
{
//There are two cases based on the position of i and right:
//1, i<=right uses known information to calculate i
//2, i>right, indicating that the position of i when not detected, can only use the center of the detection method
if (i <= rightIndex)
{
// Find the symmetry of i with respect to the front center
var iMirror = 2 * centerIndex - i; // This is the key.
// This line is the key, instead of spreading out a little bit to the left/right, as in center probing
// Reduce unnecessary probing based on known information, must choose the smaller of the two as the starting point for left/right probing
var minRadiusLength = (rightIndex - i, radiusPoints[iMirror]);
// Here the left and right -1 and +1 are because the symmetry can directly skip the corresponding radius of the echo string
radiusPoints[i] = PalindromicRadius(tmp, i - minRadiusLength - 1, i + minRadiusLength + 1);
}
else
{
//i falls to the right of rightIndex, it is not detected, only the center detection method can be used
//Here around -1 and +1, because the center point character must be a palindrome, can be skipped directly
radiusPoints[i] = PalindromicRadius(tmp, i - 1, i + 1);
}
// Greater than rightIndex, means we can update the rightmost range, also update centerIndex
if (i + radiusPoints[i] > rightIndex)
{
centerIndex = i.
rightIndex = i + radiusPoints[i];
}
// A longer palindrome radius is found, update the startIndex position of the original string
if (radiusPoints[i] > maxLength)
{
startIndex = (i - radiusPoints[i]) / 2;
maxLength = radiusPoints[i];
}
}
// return a segment from the original string based on start and maxLen
return (startIndex, maxLength);
}
//Radius of the palindromic string
public static int PalindromicRadius(string s, int leftIndex, int rightIndex)
{
// leftIndex is greater than or equal to the first character, rightIndex is less than or equal to the last character, and left and right characters are equal
while (leftIndex >= 0 && rightIndex < && s[leftIndex] == s[rightIndex])
{
//expand one bit from the center to each end
//expand to the left
--leftIndex;
//expand to the right
++rightIndex;
}
//returns the radius of the echo string (note that it should have been (rightIndex - leftIndex + 1)/2, //but after the condition was met leftIndex and rightIndex were extended to the left and right, respectively.
//But after the condition is met, leftIndex and rightIndex are expanded by one to the left and one to the right, respectively.
// Therefore, we need to subtract these two, because the center element is not returned in the calculation also need to subtract one.
//so (rightIndex - leftIndex + 1 - 2 - 1) / 2
// so the final formula is (rightIndex - leftIndex - 1)/2)
return (rightIndex - leftIndex - 2) / 2;
}
Time complexity: O(n), may be more difficult to understand is why the for nested while or O(n) time complexity? Because first of all, each character will only be expanded at most once, and secondly, when a new expansion, the current position to the newest bounded part can be obtained by symmetry without the need to expand again, so the total number of while operations will not be greater than n, plus preprocessing string n, as well as the initialization of the auxiliary array of 2n +1, so the whole is still O(n).
Space complexity: O(n), we need O(n) space to record the radius of each position.
This is the whole process of the horse-drawn cart algorithm, let's summarize again, the horse-drawn cart algorithm is the optimization of the central extension method, solving its two problems: one of the parity unified treatment, and the second use of symmetry to reduce the repeated calculations. The second point is that the symmetry does not need to start from the center every time the extension, but directly skip the part of the bit that has been calculated.
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner