网站顶部地图代码怎么做的,学习做网站的网站,山东大学经济研究院,西安网页制作培训机构一、回文字符串#xff08;Palindromic String#xff09;
回文字符串#xff08;Palindromic String#xff09;是指前、后向读起来完全相同的字符串。
回文字符串除了答题似乎没有什么用处 :P 二、求解思路
求解字符串的回文子串的基本思路#xff1a;
1、遍历每个位…一、回文字符串Palindromic String
回文字符串Palindromic String是指前、后向读起来完全相同的字符串。
回文字符串除了答题似乎没有什么用处 :P 二、求解思路
求解字符串的回文子串的基本思路
1、遍历每个位置 2、先看有没有以位置i为中心的回文串举例ABCBA。所以我们要比较i1和i-1是否相等i2和i-2是否相等一直比较到字符串某一端点结束或者中途发现不等的字符 3、再看有没有以位置i为对称中心的回文串举例ABBA。所以我们要先看i和i1等不等如果等那再看i-1和i2是否相等i-2和i3是否相等一直比较到字符串某一端点结束或者中途发现不等的字符。
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 Manachers 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 Manachers Algorithm// This code is contributed by PrinciRaj1992public 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 arrayfor (currentRightPosition 2; currentRightPosition N; currentRightPosition){// get currentLeftPosition iMirror for currentRightPosition icurrentLeftPosition 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];}// 重新计算maxLPSLengthif (lengthArray[currentRightPosition] maxLPSLength){maxLPSLength lengthArray[currentRightPosition];maxLPSCenterPosition currentRightPosition;}// 如果以currentRightPosition为中心的回文扩展到centerRightPosition之外// 根据扩展的回文调整centerPositionif (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 ;}}
}
