最长回文查找

题目

给定一个字符串,在这个字符串中找到最长的一个回文字符串,这个题目并没有什么高级的解法,形式大概是穷举的方式找出来的,但我是从最大的字符串往最小的字符串里找,以节省不必要的计算。

题解


#include <string.h>

int PalindromicString(char* s, int start, int end) {
	for (int i = start, j = end; i < j; i++, j--) {
		if (s[i] != s[j]) {
			return 0;
		}
	}
	return 1;
}

char* longestPalindrome(char* s) {
	int start = 0;
	int end = 0;
	int len = strlen(s);
	if (len == 0) {
		return 0;
	}
	for (int i = 0; i < len; i++) {
		for (int j = len - 1; j > i; j--) {
			if(j - i < end - start){
				break;
			}
			if (PalindromicString(s, i, j) == 1) {
				if (end - start + 1 < j - i + 1) {
					start = i;
					end = j;
					break;
				}
			}
		}
	}

	char * res = malloc(1001);
	memset(res, 0x00, 1001);
	for (int i = 0; start <= end; start++, i++) {
		res[i] = s[start];
	}
	return res;
}

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	char* res = longestPalindrome("ddddddddddddddddddddd");
	printf("%s", res);
//	int k = PalindromicString("bbbb", 0, 3);
//	printf("%d\n", k);
	return EXIT_SUCCESS;
}