Possible Duplicate:
Write a function that returns the longest palindrome in a given string
我知道在O(n^2)。 但似乎已经有了更好的解决办法。
I ve found ,this,与O(n)回答有联系,但在Haskell撰写,对我来说并不明确。
在c#或类似文件中找到答案是巨大的。
我已经找到了解决办法的明确解释:。 由于这一联系,Justin为此提供了帮助。
在那里,你可以发现 algorithm和 Java法的实施(C++的实施含有错误)。
这里的C#执行只是这些算法的翻译。
public static int LongestPalindrome(string seq)
{
int Longest = 0;
List<int> l = new List<int>();
int i = 0;
int palLen = 0;
int s = 0;
int e = 0;
while (i<seq.Length)
{
if (i > palLen && seq[i-palLen-1] == seq[i])
{
palLen += 2;
i += 1;
continue;
}
l.Add(palLen);
Longest = Math.Max(Longest, palLen);
s = l.Count - 2;
e = s - palLen;
bool found = false;
for (int j = s; j > e; j--)
{
int d = j - e - 1;
if (l[j] == d)
{
palLen = d;
found = true;
break;
}
l.Add(Math.Min(d, l[j]));
}
if (!found)
{
palLen = 1;
i += 1;
}
}
l.Add(palLen);
Longest = Math.Max(Longest, palLen);
return Longest;
}
这是其 j版:
public static int LongestPalindrome(String seq) {
int Longest = 0;
List<Integer> l = new ArrayList<Integer>();
int i = 0;
int palLen = 0;
int s = 0;
int e = 0;
while (i < seq.length()) {
if (i > palLen && seq.charAt(i - palLen - 1) == seq.charAt(i)) {
palLen += 2;
i += 1;
continue;
}
l.add(palLen);
Longest = Math.max(Longest, palLen);
s = l.size() - 2;
e = s - palLen;
boolean found = false;
for (int j = s; j > e; j--) {
int d = j - e - 1;
if (l.get(j) == d) {
palLen = d;
found = true;
break;
}
l.add(Math.min(d, l.get(j)));
}
if (!found) {
palLen = 1;
i += 1;
}
}
l.add(palLen);
Longest = Math.max(Longest, palLen);
return Longest;
}
public static string GetMaxPalindromeString(string testingString)
{
int stringLength = testingString.Length;
int maxPalindromeStringLength = 0;
int maxPalindromeStringStartIndex = 0;
for (int i = 0; i < stringLength; i++)
{
int currentCharIndex = i;
for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
{
if (lastCharIndex - currentCharIndex + 1 < maxPalindromeStringLength)
{
break;
}
bool isPalindrome = true;
if (testingString[currentCharIndex] != testingString[lastCharIndex])
{
continue;
}
else
{
int matchedCharIndexFromEnd = lastCharIndex - 1;
for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < matchedCharIndexFromEnd; nextCharIndex++)
{
if (testingString[nextCharIndex] != testingString[matchedCharIndexFromEnd])
{
isPalindrome = false;
break;
}
matchedCharIndexFromEnd--;
}
}
if (isPalindrome)
{
if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
{
maxPalindromeStringStartIndex = currentCharIndex;
maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
}
break;
}
}
}
if(maxPalindromeStringLength>0)
{
return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
}
return null;
}
C#
首先,我甚至连长的 p。 然后,我寻找奇迹长的 p。 当发现棕榈树时,它确定长度并相应确定最高长度。 这方面的平均复杂情况是直线性的。
protected static int LongestPalindrome(string str)
{
int i = 0;
int j = 1;
int oldJ = 1;
int intMax = 1;
int intCount = 0;
if (str.Length == 0) return 0;
if (str.Length == 1) return 1;
int[] intDistance = new int[2] {0,1};
for( int k = 0; k < intDistance.Length; k++ ){
j = 1 + intDistance[k];
oldJ = j;
intCount = 0;
i = 0;
while (j < str.Length)
{
if (str[i].Equals(str[j]))
{
oldJ = j;
intCount = 2 + intDistance[k];
i--;
j++;
while (i >= 0 && j < str.Length)
{
if (str[i].Equals(str[j]))
{
intCount += 2;
i--;
j++;
continue;
}
else
{
break;
}
}
intMax = getMax(intMax, intCount);
j = oldJ + 1;
i = j - 1 - intDistance[k];
}
else
{
i++;
j++;
}
}
}
return intMax;
}
protected static int getMax(int a, int b)
{
if (a > b) return a; return b;
}
最近,我在面谈时写过以下文字......
public string FindMaxLengthPalindrome(string s)
{
string maxLengthPalindrome = "";
if (s == null) return s;
int len = s.Length;
for(int i = 0; i < len; i++)
{
for (int j = 0; j < len - i; j++)
{
bool found = true;
for (int k = j; k < (len - j) / 2; k++)
{
if (s[k] != s[len - (k - j + 1)])
{
found = false;
break;
}
}
if (found)
{
if (len - j > maxLengthPalindrome.Length)
maxLengthPalindrome = s.Substring(j, len - j);
}
if(maxLengthPalindrome.Length >= (len - (i + j)))
break;
}
if (maxLengthPalindrome.Length >= (len - i))
break;
}
return maxLengthPalindrome;
}
我在接受面谈时就谈这个问题。
不幸的是,我发现我回家的时候。
public static string GetMaxPalindromeString(string testingString)
{
int stringLength = testingString.Length;
int maxPalindromeStringLength = 0;
int maxPalindromeStringStartIndex = 0;
for (int i = 0; i < testingString.Length; i++)
{
int currentCharIndex = i;
for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
{
bool isPalindrome = true;
if (testingString[currentCharIndex] != testingString[lastCharIndex])
{
continue;
}
for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < lastCharIndex / 2; nextCharIndex++)
{
if (testingString[nextCharIndex] != testingString[lastCharIndex - 1])
{
isPalindrome = false;
break;
}
}
if (isPalindrome)
{
if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
{
maxPalindromeStringStartIndex = currentCharIndex;
maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
}
}
break;
}
}
return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
}
What is the use of default keyword in C#? Is it introduced in C# 3.0 ?
I m the only developer in my company, and am getting along well as an autodidact, but I know I m missing out on the education one gets from working with and having code reviewed by more senior devs. ...
I m pretty new to the Objective-C world and I have a long history with .net/C# so naturally I m inclined to use my C# wits. Now here s the question: I feel really inclined to create some type of ...
I cannot figure out how to marshal a C++ CBitmap to a C# Bitmap or Image class. My import looks like this: [DllImport(@"test.dll", CharSet = CharSet.Unicode)] public static extern IntPtr ...
I have two EF entities. One has a property called HouseNumber. The other has two properties, one called StartHouseNumber and one called EndHouseNumber. I want to create a many to many association ...
How to user GhostScript DLL to convert PDF to PDF/A. I know I kind of have to call the exported function of gsdll32.dll whose name is gsapi_init_with_args, but how do i pass the right arguments? BTW, ...
Since I cannot order my dictionary, what is the best way of going about taking key value pairs and also maintaing an index?
Maybe it s something I m doing wrong. I m just learning Linq because I m bored. And so far so good. I made a little program and it basically just outputs all matches (foreach) into a label control. ...