manacher算法計算最長回文子串

1、首先說明什麼是計算"最長回文子串"：

比如字元串：ababcdedcba，該字元串内部有不止一個回文子串，包括aba、abcdedcba，那麼最長的回文子串就是abcdedcba

2、正常的辦法：

正常的辦法就是周遊，每次都根據可能的兩類情況擷取最長回文，一個是這段回文是中點是兩個相同字元，如abcdeedcba，中點是兩個e；另一個是這段回文的中點就是一個字元，如abcdedcba，中點就是e。如下：

std::string func1 (const std::string str) {
	int max = 0;
	std::string longest = "";
	for (size_t i = 0; i < str.length(); i++) {
           

//假設中點為單字元，length首先置1，然後找到一次左右相同的，length就加2
           
        
int length = 1;std::string curlongest;            
for (size_t j = 1; i - j >= 0 && i + j < str.length(); j++) {
			if (str[i - j] == str[i + j]) {
				length += 2;
				curlongest = str.substr(i - j, 1 + j * 2);
			} else {
				break;
			}
		}

		if (length > max) {
			max = length;
			longest = curlongest;
		}

           
    
//這裡一定首先判斷是否是中點雙字元的情況，某些互相抄襲的文檔的沒有這個判斷是不對的！
           
    
//length首先置2，然後找到一次左右相同的，length就加2
		if (i != str.length() - 1 && str[i] == str[i + 1]) {
			length = 2;
			for (size_t j = 1; i - j >= 0 && i + j + 1 < str.length(); j++) {
				if (str[i - j] == str[i + j + 1]) {
					length += 2;
					curlongest = str.substr(i - j, 2 + j * 2);
				} else {
					break;
				}
			}
		}

		if (length > max) {
			max = length;
			longest = curlongest;
		}
	}

	return longest;
}
           
        
 

 
這種方法比較容易想到，但遇上字元串比較多的情況，這個方法會慢點
 
 3、manacher： 
首先，manacher方法用插入符号的方式，去除了所謂中點為單字元/雙字元的問題
 
比如對于abccba，我把字元串變為1a1b1c1c1b1a1，計算的是新字元串的第一個字元a到倒數第二個字元a的回文子串長度，以前的雙中點字元cc，轉化成了計算新字元串的兩個字元c之間的字元1的回文子串，即不再有雙中點字元情況的存在了。
 

 
 
其次，manacher方法省掉了很多比較計算。
 
這個方法建立在一個定理的前提上，如對于字元串：ababa，一眼就能看出來最大回文就是ababa，中點為第三個字元a，此外還能看出對于前三個和後三個字元，均為aba，也是一個回文，中點字元分别為第2個b和第四個b；
 
那麼如果字元串改為abcbefebcba，同樣，最大回文就是字元串本身，此外還有兩個回文即兩個bcb
 
那麼如果字元串再改完xyzabcbefebcbazyx，最大回文仍然是字元串自身，此外有兩個回文還是兩個bcb
 

 
 
在第一次計算字元c的回文時，會計算到bcb，回文子串長度為3，
 
然後計算到f，發現一個巨大的回文子串即整個字元串自身，
 
然後計算下一個c，此時c處于f的回文範圍以内，那麼定理來了："在已知最大回文子串的範圍内部，範圍内部任意一個位置的字元的回文子串長度，不會超過它的對稱點的回文子串長度"
 
試想下，對于abcbefebcba111111，最大回文子串是中點為f的整個字元串本身，第二個c字元在這個回文子串的範圍内，那麼如不考慮後面的11111，它的回文子串長度肯定不會超過它的對稱點的回文子串長度的，如果能超過，那麼f的回文子串不可能是整個字元串本身還要更長，但實際不可能更長。
 
這能省去很多計算，如下：
 
        
//在原字元串插入字元1，如abcba，變成1a1b1c1b1a1
           
    
std::string insert_symbol (const std::string str) {
	std::string newstr = "";
	for (size_t i = 0; i < str.length(); i++) {
		newstr += "1";
		newstr += str[i];
	}
	newstr += "1";
	return newstr;
}

std::string func2 (const std::string str) {
           
    
//生成新字元串newstr
	std::string newstr = insert_symbol(str);
           
    
//mx指的是，點位置+回文子串半價長度，最大的一個點，所伸展到字元串的位置，比如44444abcdedcba55555，(點位置+回文半徑)最大的一個點是e，            
所伸展到字元串的位置是最後一個字元a的位置，即mx。id即這個點的位置。
           
        
 int mx = 0, id = 0;                
//數組p，用于記錄每個點的回文子串的半徑長度，如abadedaba，對于e，它的長度是4，對于第一個b，長度為1。
           
    
int *p = new int[newstr.length()];
	memset(p, 0, sizeof(int) * newstr.length());
	for (int i = 1; i < newstr.length() - 1; i++) {
		//first get the minest of p[i](http://blog.csdn.net/xingyeyongheng/article/details/9310555)
		//if i is in range of previous huiwen, could calc part of huiwen in range mx for i, because in range not out of mx, the huiwen part of i could not bigger than mx
		//but out of mx, huiwen part of i still need calc
           
    
//這個是核心。落在mx内的點初始化時的半徑是不可能越過mx的。這個不太容易說的清晰，一定要仔細想，一定要了解
		if (mx > i) {
			p[i] = ((mx - i) < p[id * 2 - i])?(mx - i):p[id * 2 - i];
		} else {
			p[i] = 0;
		}

           
    
//計算越過mx後的部分是不是還存在更長的回文子串的可能
           
    
//then actual calc p[i], because maybe (i + p[i]) is longer that out of mx
		int cur = p[i];
		for (int j = 1; i - cur - j >= 0 && i + cur + j < newstr.length(); j++) {
			if (newstr[i + cur + j] == newstr[i - cur - j]) {
				p[i]++;
			} else {
				break;
			}
		}
		
           
    
//下面兩個判斷是獨立的，不可以寫在一個if裡，否則可以試試(有些互相抄襲的文章是寫在一個if裡的。。。)
           
    
//首先判斷伸展範圍mx是否變的更大了
		if (mx < i + p[i]) {
			mx = i + p[i];
		}
           
    
//然後判斷半徑最長的id是不是該換人了
		if (p[id] < p[i]) {
			id = i;
		}
	}

           
    
//id是半徑最長的點，即最大回文子串的中點，p[id]是它的半徑，可以通過這個計算出最長回文子串是什麼
	std::string longest = "";
	for (size_t i = id - p[id]; i <= id + p[id]; i++) {
		if (newstr[i] != '1') {
			longest += newstr[i];
		}
	}

	delete [] p;
	return longest;
}
           
        
如下是測試程式：
        
//随便多試試
	std::string str = "abcbabcdedcbabcdefghgfedcba";
           
    
str = argv[1];
	std::cout << func1(str) << std::endl;
	std::cout << func2(str) << std::endl;
	return 0;
}
           
        

 
 描述的不太清楚，回來再補上清晰的描述