重複の可能性：
指定された文字列で最長の回文を返す関数を記述します
私はO（n ^ 2）でこれを行う方法を知っています。しかし、もっと良い解決策があるようです。
私はこれを見つけました、そしてO（n）の答えへのリンクがあります、しかしそれはHaskellで書かれていて、私には明確ではありません。
C＃などで答えを得るのは素晴らしいことです。
22331 次
6 に答える
6
私はここで解決策の明確な説明を見つけました。このリンクを提供してくれたJustinに感謝します。
そこで、アルゴリズムのPythonおよび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;
}
于 2010-04-26T12:58:32.467 に答える
1
そしてこれはそのjavaバージョンです：
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;
}
于 2012-02-20T14:34:28.997 に答える
0
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;
}
于 2013-01-04T02:44:37.753 に答える
0
C＃
まず、偶数の長さの回文を検索します。次に、奇数の長さの回文を検索します。回文を見つけると、長さを決定し、それに応じて最大長を設定します。この場合の平均的なケースの複雑さは線形です。
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;
}
于 2013-06-29T22:58:53.200 に答える
-1
最近、インタビュー中に次のコードを書きました...
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;
}
于 2012-06-15T04:50:18.440 に答える
-1
面接を受けたときにこの質問がありました。
残念ながら、家に帰ったときに知りました。
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);
}
于 2012-12-20T13:48:49.223 に答える