C#，求最长回文字符串的马拉车（Manacher）算法的源代码

一、回文字符串（Palindromic String）

回文字符串（Palindromic String）是指前、后向读起来完全相同的字符串。

回文字符串除了答题似乎没有什么用处 :P

二、求解思路

求解字符串的回文子串的基本思路：

1、遍历每个位置；
2、先看有没有以位置i为中心的回文串（举例ABCBA）。所以我们要比较i+1和i-1是否相等，i+2和i-2是否相等，一直比较到字符串某一端点结束，或者中途发现不等的字符；
3、再看有没有以位置i为对称中心的回文串（举例ABBA）。所以我们要先看i和i+1等不等，如果等，那再看i-1和i+2是否相等，i-2和i+3是否相等，一直比较到字符串某一端点结束，或者中途发现不等的字符。

Manacher算法是一位名叫Manacher的人在1975年提出的一种算法，解决的问题是求最长回文子串。Manacher算法的核心思路就是利用之前求得的臂长( 即之前求出的Len值) 来减少时间复杂度，也就是说通过前面求出的Len值来加速求出当前下标i的 Len[i]，快速求出所有的Len?值就是该算法的目的。

速度！

三、源代码

3.1 文本格式

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?// C# program to implement Manacher's Algorithm
?? ?// This code is contributed by PrinciRaj1992
?? ?public static class Palindromic_String
?? ?{
?? ??? ?public static string Manacher(string text)
?? ??? ?{
?? ??? ??? ?int N = text.Length;
?? ??? ??? ?if (N == 0)
?? ??? ??? ?{
?? ??? ??? ??? ?return "";
?? ??? ??? ?}
?? ??? ??? ?N = 2 * N + 1;

?? ??? ??? ?int[] lengthArray = new int[N + 1];
?? ??? ??? ?lengthArray[0] = 0;
?? ??? ??? ?lengthArray[1] = 1;

?? ??? ??? ?int centerPosition = 1;
?? ??? ??? ?int centerRightPosition = 2;
?? ??? ??? ?int currentRightPosition = 0;
?? ??? ??? ?int currentLeftPosition;
?? ??? ??? ?int maxLPSLength = 0;
?? ??? ??? ?int maxLPSCenterPosition = 0;
?? ??? ??? ?int start = -1;
?? ??? ??? ?int end = -1;
?? ??? ??? ?int diff = -1;

?? ??? ??? ?// Uncomment it to print LPS Length array
?? ??? ??? ?for (currentRightPosition = 2; currentRightPosition < N; currentRightPosition++)
?? ??? ??? ?{
?? ??? ??? ??? ?// get currentLeftPosition iMirror for currentRightPosition i
?? ??? ??? ??? ?currentLeftPosition = 2 * centerPosition - currentRightPosition;
?? ??? ??? ??? ?lengthArray[currentRightPosition] = 0;
?? ??? ??? ??? ?diff = centerRightPosition - currentRightPosition;

?? ??? ??? ??? ?// 如果 currentRightPosition 范围内
?? ??? ??? ??? ?if (diff > 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?lengthArray[currentRightPosition] = Math.Min(lengthArray[currentLeftPosition], diff);
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 尝试扩展以 currentRightPosition i为中心的回文。
?? ??? ??? ??? ?// 对于奇数位置，我们比较字符，如果匹配，则将LPS长度增加1。
?? ??? ??? ??? ?// 即使是位置，我们只是将LPS增加1，而不进行任何字符比较。
?? ??? ??? ??? ?while (((currentRightPosition + lengthArray[currentRightPosition]) + 1 < N && (currentRightPosition - lengthArray[currentRightPosition]) > 0) &&
?? ??? ??? ??? ??? ?(((currentRightPosition + lengthArray[currentRightPosition] + 1) % 2 == 0) ||?
?? ??? ??? ??? ??? ?(text[(currentRightPosition + lengthArray[currentRightPosition] + 1) / 2] == text[(currentRightPosition - lengthArray[currentRightPosition] - 1) / 2])))
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?lengthArray[currentRightPosition]++;
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 重新计算maxLPSLength
?? ??? ??? ??? ?if (lengthArray[currentRightPosition] > maxLPSLength)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?maxLPSLength = lengthArray[currentRightPosition];
?? ??? ??? ??? ??? ?maxLPSCenterPosition = currentRightPosition;
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 如果以currentRightPosition为中心的回文扩展到centerRightPosition之外，
?? ??? ??? ??? ?// 根据扩展的回文调整centerPosition
?? ??? ??? ??? ?if (currentRightPosition + lengthArray[currentRightPosition] > centerRightPosition)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?centerPosition = currentRightPosition;
?? ??? ??? ??? ??? ?centerRightPosition = currentRightPosition + lengthArray[currentRightPosition];
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?start = (maxLPSCenterPosition - maxLPSLength) / 2;
?? ??? ??? ?end = start + maxLPSLength - 1;
?? ??? ??? ?if (end > start)
?? ??? ??? ?{
?? ??? ??? ??? ?StringBuilder sb = new StringBuilder();
?? ??? ??? ??? ?for (int i = start; i <= end; i++)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?sb.Append(text.Substring(i, 1));
?? ??? ??? ??? ?}
?? ??? ??? ??? ?return sb.ToString();
?? ??? ??? ?}
?? ??? ??? ?return "";
?? ??? ?}
?? ?}
}
?

-------------------------------------------------------

POWER BY TRUFFER.CN

3.2 代码格式

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?// C# program to implement Manacher's Algorithm
?? ?// This code is contributed by PrinciRaj1992
?? ?public static class Palindromic_String
?? ?{
?? ??? ?public static string Manacher(string text)
?? ??? ?{
?? ??? ??? ?int N = text.Length;
?? ??? ??? ?if (N == 0)
?? ??? ??? ?{
?? ??? ??? ??? ?return "";
?? ??? ??? ?}
?? ??? ??? ?N = 2 * N + 1;

?? ??? ??? ?int[] lengthArray = new int[N + 1];
?? ??? ??? ?lengthArray[0] = 0;
?? ??? ??? ?lengthArray[1] = 1;

?? ??? ??? ?int centerPosition = 1;
?? ??? ??? ?int centerRightPosition = 2;
?? ??? ??? ?int currentRightPosition = 0;
?? ??? ??? ?int currentLeftPosition;
?? ??? ??? ?int maxLPSLength = 0;
?? ??? ??? ?int maxLPSCenterPosition = 0;
?? ??? ??? ?int start = -1;
?? ??? ??? ?int end = -1;
?? ??? ??? ?int diff = -1;

?? ??? ??? ?// Uncomment it to print LPS Length array
?? ??? ??? ?for (currentRightPosition = 2; currentRightPosition < N; currentRightPosition++)
?? ??? ??? ?{
?? ??? ??? ??? ?// get currentLeftPosition iMirror for currentRightPosition i
?? ??? ??? ??? ?currentLeftPosition = 2 * centerPosition - currentRightPosition;
?? ??? ??? ??? ?lengthArray[currentRightPosition] = 0;
?? ??? ??? ??? ?diff = centerRightPosition - currentRightPosition;

?? ??? ??? ??? ?// 如果 currentRightPosition 范围内
?? ??? ??? ??? ?if (diff > 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?lengthArray[currentRightPosition] = Math.Min(lengthArray[currentLeftPosition], diff);
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 尝试扩展以 currentRightPosition i为中心的回文。
?? ??? ??? ??? ?// 对于奇数位置，我们比较字符，如果匹配，则将LPS长度增加1。
?? ??? ??? ??? ?// 即使是位置，我们只是将LPS增加1，而不进行任何字符比较。
?? ??? ??? ??? ?while (((currentRightPosition + lengthArray[currentRightPosition]) + 1 < N && (currentRightPosition - lengthArray[currentRightPosition]) > 0) &&
?? ??? ??? ??? ??? ?(((currentRightPosition + lengthArray[currentRightPosition] + 1) % 2 == 0) ||?
?? ??? ??? ??? ??? ?(text[(currentRightPosition + lengthArray[currentRightPosition] + 1) / 2] == text[(currentRightPosition - lengthArray[currentRightPosition] - 1) / 2])))
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?lengthArray[currentRightPosition]++;
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 重新计算maxLPSLength
?? ??? ??? ??? ?if (lengthArray[currentRightPosition] > maxLPSLength)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?maxLPSLength = lengthArray[currentRightPosition];
?? ??? ??? ??? ??? ?maxLPSCenterPosition = currentRightPosition;
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 如果以currentRightPosition为中心的回文扩展到centerRightPosition之外，
?? ??? ??? ??? ?// 根据扩展的回文调整centerPosition
?? ??? ??? ??? ?if (currentRightPosition + lengthArray[currentRightPosition] > centerRightPosition)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?centerPosition = currentRightPosition;
?? ??? ??? ??? ??? ?centerRightPosition = currentRightPosition + lengthArray[currentRightPosition];
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?start = (maxLPSCenterPosition - maxLPSLength) / 2;
?? ??? ??? ?end = start + maxLPSLength - 1;
?? ??? ??? ?if (end > start)
?? ??? ??? ?{
?? ??? ??? ??? ?StringBuilder sb = new StringBuilder();
?? ??? ??? ??? ?for (int i = start; i <= end; i++)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?sb.Append(text.Substring(i, 1));
?? ??? ??? ??? ?}
?? ??? ??? ??? ?return sb.ToString();
?? ??? ??? ?}
?? ??? ??? ?return "";
?? ??? ?}
?? ?}
}