首页 > ACM题库 > 九度OJ > 九度-1528-最长回文子串[解题代码]
2013
12-13

九度-1528-最长回文子串[解题代码]

题目来源:腾讯2013年实习生招聘二面面试题

题目描述:

回文串就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
回文子串,顾名思义,即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c…x,y,z组成的字符串,请输出其中最长的回文子串的长度。

输入:

输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c…x,y,z组成的字符串,字符串的长度不大于200000。

输出:

对于每组测试用例,输出一个整数,表示该组测试用例的字符串中所包含的的最长回文子串的长度。

样例输入:
abab
bbbb
abba
样例输出:
3
4
4

cpp 代码如下:
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int M = 200010;
char str[M * 2], sb[M];
int p[M * 2];

int pre() {
	str[0] = '$';
	int j = 1;
	for (int i = 0; sb[i]; i++) {
		str[j++] = '#';
		str[j++] = sb[i];
	}
	str[j++] = '#';
	str[j] = 0;
	return j;
}

int manacher(int n) {
	int mx = 0; //记录前面回文串最长影响到的地方。不一定是最长回文串造成的。
	int id; //最长影响串的ID;
	p[0] = 0;
	int i;
	int ans = 0;
	for (i = 1; i < n; i++) {
		p[i] = 1;
		if (mx > i) { //2*id-i是i关于id的对称点相当于是id-(i-id);
			p[i] = p[2 * id - i];

			//由于对称点的回文半径可能超过mx-i,因为mx后面的还没有配过
			//所以要取小的。等等继续配
			if (mx - i < p[i])
				p[i] = mx - i;
		}
		while (str[i - p[i]] == str[i + p[i]])
			p[i]++;
		if (i + p[i] > mx) {
			mx = i + p[i];
			id = i;
		}
		if (ans < p[i])
			ans = p[i];
	}

	return ans;
}

int main() {
	while(gets(sb)) {
		int n = pre();
		printf("%d\n",manacher(n)-1);
	}
	return 0;
}

/**************************************************************
	Problem: 1528
	User: coder
	Language: C++
	Result: Accepted
	Time:60 ms
	Memory:3668 kb
****************************************************************/


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count