manacher-線性查找演算法-(最長迴文子串問題)

#ifndef MANACHER_ARRAY_H_
#define MANACHER_ARRAY_H_

// 功能: 最長迴文子串的長度.
// 參數: s(字元串首地址).
// 返回: 最長迴文子串的長度.
// 註意: 當 s=NULL 時, 將錯誤退出程式.
extern int32_t manacherArray( char s[] );

#endif

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "manacherArray.h"

// 功能: 列印錯誤信息後就錯誤退出程式.
// 參數: expression(錯誤判斷表達式), message(需列印的錯誤信息).
// 返回: 無.
// 註意: 當表達式 expression 為真時, 才觸發.
#define ERROR_EXIT( expression, message )                                    \
if( (expression) ) {                                                         \
	fprintf( stderr, "\nerror location: file = %s, func = %s, line = %d.\n", \
	                 __FILE__, __func__, __LINE__ );                         \
	fprintf( stderr, "error  message: %s%s.\n\a",                            \
	                 (message) != NULL ? (message) : __func__,               \
	                 (message) != NULL ? "" : " function error" );           \
	exit( EXIT_FAILURE );                                                    \
}

• 萌新版本。

  int32_t manacherArray( char s[] ) {
  	char *tempA = NULL, ch = '#';
  	int *radiusA = NULL; // 迴文半徑數組.
  	int right = -1;      // 迴文最右邊界.
  	int center = -1;     // 首次迴文中心.
  	int left = -1;       // 以 center 為迴文中心的迴文左邊界.
  	int mirror = -1;     // i 以 center 為中心的鏡像 i'.
  	int mirrorLeft = -1; // 以 i' 為迴文中心的迴文左邊界.
  	int i = 0, j = 1, answer = 0, slen = 0;
  
  	ERROR_EXIT( s == NULL, "NullPointerException" );
  	slen = strlen( s );
  	tempA = malloc( sizeof(*tempA) * (slen * 2 + 2) );
  	for( tempA[0] = ch; (tempA[j++] = s[i++]) != '\0'; tempA[j++] = ch ) {}
  	radiusA = malloc( sizeof(*radiusA) * (slen * 2 + 1) );
  
  	for( i = 0; tempA[i] != '\0'; ++i ) {
  		if( i > right ) {
  			// i位置在迴文最右邊界外, 暴力擴.
  			for( j = 1; i - j >= 0 && tempA[i - j] == tempA[i + j]; ++j ) {}
  			radiusA[i] = j - 1;
  		} else {
  			left = center - radiusA[center];       // 以 center 為迴文中心的迴文左邊界.
  			mirror = center * 2 - i;               // i 以 center 為中心的鏡像 i'.
  			mirrorLeft = mirror - radiusA[mirror]; // 以 i' 為迴文中心的迴文左邊界.
  			// i位置在迴文最右邊界裡面,根據以 i' 為迴文中心的迴文左邊界又可分為3種情況.
  			if( mirrorLeft == left ) {
  				for( j = right - i + 1; i - j >= 0 && tempA[i - j] == tempA[i + j]; ++j ) {}
  				radiusA[i] = j - 1;
  			} else if( mirrorLeft < left ) {
  				radiusA[i] = right - i;
  			} else {
  				radiusA[i] = radiusA[mirror];
  			}
  		}
  		if( i + radiusA[i] > right ) { // 出現較右的迴文右邊界.
  			center = i;
  			right = i + radiusA[i];
  		}
  		if( radiusA[i] > answer ) {    // 出現較大的迴文半徑.
  			answer = radiusA[i];
  		}
  	}
  	free( radiusA );
  	free( tempA );
  
  	return answer;
  }
  

• 左神版本。

  char *manacherArray( char s[] ) {
  	char *ta = NULL, ch = '#';
  	int *radius = NULL;  // 迴文半徑數組.
  	int right = -1;      // 出現過的迴文最右邊界.
  	int center = -1;     // 第一次出現迴文最右邊界時的迴文中心.
  	int answer = -1;
  	int i = 0, j = 1, slen = 0;
  
  	ERROR_EXIT( s == NULL, "NullPointerException" );
  	slen = strlen( s );
  	ta = malloc( sizeof(*ta) * (slen * 2 + 2) );
  	for( ta[0] = ch; (ta[j++] = s[i++]) != '\0'; ta[j++] = ch ) {}
  	radius = malloc( sizeof(*radius) * (slen * 2 + 1) );
  
  	for( i = 0; ta[i] != '\0'; ++i ) {
  		// i在迴文最右邊界外,讓 radius[i] 預設取只有自己本身距離1.
  		// i在迴文最右邊界內,讓 radius[i] 預設取較短的距離, 因為較長距離會越界或不是迴文.
  		// center * 2 - i 表示 i位置的鏡像i'.
  		radius[i] = i >= right ? 1 : MIN( radius[center * 2 - i], right - i );
  
  		// 為什麼 while 迴圈 不用判斷 i + radius[i] < strlen( ta ) 呢?
  		// ∵ 迴圈中判斷了 i - radius[i] >= 0.
  		// ∴ 在迴圈中 i + radius[i] 是合法索引不會引發越界.
  		// ∵ i 和 radius[i] 不會是負數 且 radius[i]在迴圈開始前的預設最小值是1.
  		// ∴ i - radius[i] 位置 永遠在 i + radius[i] 位置 前面.
  		// ∵ radius[i] 在迴圈中的增長值是1.
  		// ∴ '\0'出現的位置一定是在 i + radius[i] 位置.
  		while( i - radius[i] >= 0 && ta[i - radius[i]] == ta[i + radius[j]] ) {
  			++radius[i];
  		}
  
  		--radius[i]; // 減去i位置自己本身距離1.
  
  		if( i + radius[i] > right ) { // 出現較右的迴文右邊界.
  			center = i;
  			right = i + radius[i];
  		}
  		if( radius[i] > answer ) {    // 出現較大的迴文半徑.
  			answer = radius[i];
  		}
  	}
  	free( radius );
  	free( ta );
  
  	return answer;
  }
  

實現對數器

# !/bin/bash

for(( i = 1; i <= 21; ++i )) do
	printf "%02d" ${i}
	echo -n ______________
	./manacherArrayTest
done