原题链接
这道题用的算法时间复杂度是O(n^2) 学有余力的同学可以去看看“马拉车算法”,那个算法解这道题时间复杂度是O(n),但是这个算法这道题也可以过。
大概思想如下:
首先最外面套一层循环,从第一个字符遍历到最后一个字符。

  1. 如果对称子串是奇数串,那么最中间的字符我们就不管了。对称子串当前最大长度为1,这时i-j表示指向第i个字符变量左边第j个字符,i+j表示指向第i个字符变量右边第j个字符。如果左右指向的变量越界或者不相等,那么退出循环,否则当前最大长度加2.
  2. 如果对称字串是偶数串,此时对称子串当前最大长度为0。这时i-j+1表示指向第i+1个字符变量左边第j个字符,i+j表示指向第i个字符变量右边第j个字符。如果左右指向的变量越界或者不相等,那么退出循环,否则当前最大长度加2.

具体代码如下:

#include <stdio.h>
#include <string.h>
int main(){
	char c[2000];
	gets(c);
	int i,max=0,tmp,j,len=strlen(c);
	for(i=0;i<len;i++){
		tmp=1;
		for(j=1;j<len;j++){
			if(i-j<0 || i+j>=len || c[i-j]!=c[i+j]){
				break;
			}
			tmp+=2;
		}
		if(tmp>max){
			max=tmp;
		}
		tmp=0;
		for(j=1;j<len;j++){
			if(i-j+1<0 || i+j>=len || c[i-j+1]!=c[i+j]){
				break;
			}
			tmp+=2;
		}
		if(tmp>max){
			max=tmp;
		}
	}
	printf("%d",max);
} 

更多推荐