Fetching contributors…
Cannot retrieve contributors at this time
109 lines (82 sloc) 5.14 KB

## 最长回文子串

### 分析与解法

#### 解法一

```int LongestPalindrome(const char *s, int n)
{
int i, j, max,c;
if (s == 0 || n < 1)
return 0;
max = 0;

for (i = 0; i < n; ++i) { // i is the middle point of the palindrome
for (j = 0; (i - j >= 0) && (i + j < n); ++j){ // if the length of the palindrome is odd
if (s[i - j] != s[i + j])
break;
c = j * 2 + 1;
}
if (c > max)
max = c;
for (j = 0; (i - j >= 0) && (i + j + 1 < n); ++j){ // for the even case
if (s[i - j] != s[i + j + 1])
break;
c = j * 2 + 2;
}
if (c > max)
max = c;
}
return max;
}```

#### 解法二、O(N)解法

• S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
• P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1

• 如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i)

C代码如下：

```//mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)
//故谁小取谁
if (mx - i > P[2*id - i])
P[i] = P[2*id - i];
else  //mx-i <= P[2*id - i]
P[i] = mx - i; ```

```//输入，并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++)
{
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (s[i + p[i]] == s[i - p[i]])
p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的```

You can’t perform that action at this time.