leetcode 5. 最長回文子列暴力法、中心拡張アルゴリズム、動的計画、マラ車アルゴリズム(Manacher Algorithm)
4961 ワード
s， s 。 s 1000。
1：
: "babad"
: "bab"
: "aba" まず、テーマを理解することが重要です!!!返事は何ですか.
[1] ， ， ， ， 。この問題は時間の複雑さには要求していないが、それでも最初は仕方がない.しばらく考えて、遍歴して、俗に暴力法と呼ばれて、結局問題を解決するのが最も重要で、最適化は引き続きすることができます.簡単な解析から,回文の文字列は2つの対応が等しいことが分かる.長さnの返信文字列を仮定し、以下の条件を満たす
s[i] == s[n-i-1]与えられた文字列の各文字を巡り、その文字列で始まる最長の回文文字列を見つけます.与えられた開始文字について、最も長いことを考慮すると、文字列の末尾から後へ遍歴するに違いありません.firstを使用して、lastの2つのポインタはそれぞれ先頭を指し、first>lastまで遍歴すると遍歴が終了し、得られた長さと開始位置が保持されます.次の文字ループを開始します.
遍歴の過程で,上述した暴力法が最適化できることが分かったが,例を挙げると,s[i]の最長回文サブシリアルテールポインタはs[j]であり,iの次の要素s[i+1]を遍歴すると,s[i+1]とs[j-1]が回文になるまで前のステップで行けるので,j+1~lastの区間を遍歴するだけでよい.同様に、後続の各要素については、末尾要素から以前の最近の返信文字まで遍歴するだけでよい.各先頭文字first[i]に対して、その対応する最長回文サブシリアル文字がlast[i]であると仮定し、先頭文字first[j](i
char * longestPalindrome(char * s){
int first, last, len = 0, i, j, max = 0, cursor, jump = 0;
char *ps = s;
if (!s)
return s;
while(*ps++ != '\0')len++;
//
for (i = 0; i < len; i++)
{
for (j = len - 1; j >= jump; j--)
{
first = i, last = j;
while (first <= last){
if (s[first++] != s[last--])
break;
}
if (s[first-1] == s[last+1]){
if (j - i + 1 > max)
{
max = j - i + 1;
cursor = i;
}
//jump ，i jump
// 。
jump = jump > last + 1 ? jump: (last + 1);
break;
}
}
}
ps = s + cursor;
if (max < len)
ps[max] = '\0';
return ps;
}
暴力遍歴法は時間的複雑度がO(n^3),中心拡張法は時間的複雑度がO(n^2)であり,この方法は実はかなり簡単である.暴力遍歴文列方向が両端から中間にマッチしているとすれば、中心拡張方向は中心から両端に及ぶ.ここで中心は奇数中心Nと偶数中心N−1を含む2 N−1個である.中心拡張メソッドは、中心から両端に遍歴し、不一致に遭遇すると終了します.
#define MAX(a,b) ((a)>(b)?(a):(b))
int centerExpand(char *s, int len, int left, int right)
{
while(left >= 0 && right < len && s[left] == s[right])
{
left--;
right++;
}
return right - left - 1;
}
char * longestPalindrome(char * s){
int len = 0, center = 0, max = 0, max0 = 0, max1 = 0, cursor = 0;
char *pStr = s;
if (!s)return s;
while (*pStr++ != '\0')len++;
for (center = 0; center < len; center++)
{
max0 = centerExpand (s, len, center, center);
max1 = centerExpand (s, len, center, center+1);
if (max < max0 || max < max1)
{
if (max0 > max1)
cursor = center - max0 / 2;
else
cursor = center + 1 - max1 /2;
max = MAX(max0, max1);
}
}
pStr = s + cursor;
if (max != len)
pStr[max] = '\0';
return pStr;
}3つ目はダイナミックプランニングで、これは私が覚えてから書きます.
=========================================================================================
動的計画の基本手順は次のとおりです.
1.段階別
2.状態繰返し方程式
3.最適解を求める.
この問題はダイナミックプランニングを使用する場合、iとjがそれぞれ文字の位置を表し、m[i][j]が文字iからjが回文文字列であるかどうかを表すm[i][j]タイプを使用することは明らかである.もしそうならm[i][j]=1;そうでなければm[i][j]=0;繰返し方程式はm[i][j]=m[i+1][j-1]&&(s[i]==s[j]);長さ1と2のm[][]値を先に算出することができます.
m[i][i] = 1; m[i][i+1] = (s[i] == s[i+1]);次に、最も長い返信文字列値max=j-i+1を記録することができる.起点はi.
難易度は大きくないが,通常動的計画を用いる場合m[i][j]が最適解を表すために用いられ,本題は状態のみが保存されているとは容易に考えられない.もっと練習しなければなりません.
次に、動的計画のcコードを示します.
char * longestPalindrome(char * s){
int i,j,d, len = 0, m[1001][1001]={0}, max = 1, c = 0;
char *pStr = s;
if (!s)return s;
while (*pStr++ != '\0')len++;
if (len <= 1)
return s;
// ，
for (i = 0; i < len - 1; i++)
{
m[i][i] = 1;
if (s[i] == s[i+1])
{
m[i][i+1] = 1;
if (max < 2)
{
max = 2;
c = i;
}
}
else
m[i][i+1] = 0;
}
m[i][i] = 1;
// ， 3 n-1
for (d = 2; d < len; d++)
for (i = 0; i + d < len; i++)
{
j = d + i;
m[i][j] = (m[i+1][j-1]) && (s[i] == s[j]);
if (m[i][j] && (j-i+1) > max)
{
max = j - i + 1; c = i;
}
}
s = s + c;
s[max] = '\0';
return s;
}
=============================================================================================
Linuxアプリケーション、カーネル、ドライバ、バックグラウンド開発交流討論群(745510310)、興味のある学生はグループ討論、交流、資料検索などを加えることができて、前進する道の上で、あなたは一人ではありません^^.