leetcode-5. 最長回文子串

char *longestPalindrome( char *s ) {
	char *answer = NULL, tempS[2002] = "#";
	int i = 0, j = 0, count[2] = {0};

	answer = malloc( sizeof(char *) * 1000 );

	for( j = 1, i = 0; s[i] != '\0'; ++i ) {
		tempS[j++] = s[i];
		tempS[j++] = '#'; // 在每個字符后面都加上'#'.
	}
	for( i = 0; tempS[i] != '\0'; ++i ) {
		// 探測以i為中心向兩邊擴展的最大偏移量.
		for( j = 1; i - j >= 0 && tempS[i + j] != '\0' && tempS[i - j] == tempS[i + j]; ++j ) {}
		if( j - 1 > count[0] ) {
			count[0] = j - 1;       // 以i為中心向兩邊擴展的偏移量, 不包括中心點.
			count[1] = i - (j - 1); // 以i為中心的左邊界.
		}
	}
	for( i = count[1], j = 0; j < count[0]; ++i ) {
		char ch = tempS[i];
		if( ch != '#' ) {
			answer[j++] = ch;
		}
	}
	answer[j] = '\0';

	return answer;
}

參考:
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

char *longestPalindrome( char *s ) {
	char *answer = NULL;
	int *dp = NULL, slen = strlen( s );
	int i = 0, j = 0, sub = 0, start = 0, max = 1;

	if( slen < 2 ) {
		return s;
	}
	answer = malloc( sizeof(*answer) * (slen + 1) );
	dp = malloc( sizeof(*dp) * slen * slen );
	for( sub = 1; sub <= slen; ++sub ) {        // sub表示子串長度.
		for( i = 0; i + sub - 1 < slen; ++i ) { // 以i位置為起點.
			j = i + sub - 1;                    // 以j位置為終點.
			if( sub == 1 ) {
				dp[i * slen + j] = 1;
			} else if( sub == 2 ) {
				dp[i * slen + j] = s[i] == s[j];
			} else {
				dp[i * slen + j] = s[i] == s[j] && dp[(i + 1) * slen + (j - 1)];
			}
			if( dp[i * slen + j] ) {
				start = i;
				max = sub;
			}
		}
	}
	free( dp );
	for( i = 0; i < max; ++i ) {
		answer[i] = s[start + i];
	}
	answer[i] = '\0';

	return answer;
}

char *longestPalindrome( char *s ) {
	char *answer = NULL, *ta = NULL, ch = '#';
	int i = 0, j = 0, slen = strlen( s );
	int *radius = NULL;  // 回文半徑陣列.
	int right = -1;      // 出現過的回文最右邊界.
	int center = -1;     // 第一次出現回文最右邊界時的回文中心.
	int left = -1;       // 以 center 為回文中心的回文左邊界.
	int mirror = -1;     // i 以 center 為中心的鏡像 i'.
	int mirrorLeft = -1; // 以 i' 為回文中心的回文左邊界.
	int mRadius = -1, mCenter = -1;

	answer = malloc( sizeof(*answer) * (slen + 1) );
	ta = malloc( sizeof(*ta) * (slen * 2 + 2) );
	for( ta[j++] = ch; (ta[j++] = s[i++]) != '\0'; ta[j++] = ch ) {}
	radius = malloc( sizeof(*radius) * (slen * 2 + 1) );

	for( i = 0; ta[i] != '\0'; ++i ) {
		if( i > right ) {
			// i位置在回文最右邊界外, 暴力擴.
			for( j = 1; i - j >= 0 && ta[i - j] == ta[i + j]; ++j ) {}
			radius[i] = j - 1;
		} else {
			left = center - radius[center];       // 以 center 為回文中心的回文左邊界.
			mirror = center * 2 - i;              // i 以 center 為中心的鏡像 i'.
			mirrorLeft = mirror - radius[mirror]; // 以 i' 為回文中心的回文左邊界.
			// i位置在回文最右邊界內,根據 i' 的回文左邊界又可分為3種情況.
			if( mirrorLeft < left ) {
				radius[i] = right - i;
			} else if( mirrorLeft == left ) {
				for( j = right - i + 1; i - j >= 0 && ta[i - j] == ta[i + j]; ++j ) {}
				radius[i] = j - 1;
			} else {
				radius[i] = radius[mirror];
			}
		}
		if( i + radius[i] > right ) { // 出現較右的回文右邊界.
			center = i;
			right = i + radius[i];
		}
		if( radius[i] > mRadius ) {   // 出現較大的回文半徑.
			mCenter = i;
			mRadius = radius[i];
		}
	}
	free( radius );
	i = mCenter - mRadius; // 最長回文的左邊界.
	j = mCenter + mRadius; // 最長回文的右邊界.
	for( right = 0; i <= j; ++i ) {
		if( ta[i] != ch ) {
			answer[right++] = ta[i];
		}
	}
	answer[right] = '\0';
	free( ta );

	return answer;
}