palindromes.cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 43 行

//原始方法是确定首位为i，尾为j，再判断S[i...j]是否为回文
//时间复杂度为 O(N^3)
//优化一下，很多次的扫描有重复的地方
//如：abba，因为bb是回文，又因为首尾都是a，所以abba也是回文
//所以我们先确定一个中心轴，再向左和右扫描，碰到不同的就停止，因为一位不同后面就不可能是回文了
//时间复杂度为 O(N^2)
//注意中心轴有2种，如：abba和abcba的中心轴区别
#include <cstdio>
#include <string>

char str[5100];
int total;

int main()
{
	int len,half_len;
	int total,i,j;
	while (gets(str)) {
		total = 0;
		len = strlen(str);
		for (i=0;i<len;i++) {
			for (j=1;j<len;j++) {
				if (i-j>=0 && i+j<len) {
					if (str[i-j] != str[i+j]) {
						break;
					}
					total++;
				}
				else	break;
			}
			for (j=1;j<len;j++) {
				if (i-j+1>=0 && i+j<len) {
					if (str[i-j+1] != str[i+j]) {
						break;
					}
					total++;
				}
				else	break;
			}
		}
		printf("%d\n",total+len);
	}
}