算法题，c++，查找字符串中的最长回文字段，遍历字符，中心扩散查询

算法题，c++，查找字符串中的最长回文字段，遍历字符，中心扩散查询 算法题，c++，查找字符串中的最长回文字段，遍历字符中心扩散查询

从给定的字符串中找出最长的回文字段，这里使用的方法是：
1、挨个遍历字符串中的每个字符，
2、每到一个字符，就查看其前一个字符和后一个字符是否相等
3、当前字符位置记录为位置iPos，前后相同字符的数量记录为偏移量iDeviation

注意判断条件：
1、最往前是字符串头，最往后是字符串尾，，不能越界，这是重要的判断条件
2、挨个遍历字符默认每一个回文字段是奇数位，但有偶数位的情况，因此需要将偶数位的判断放在前面，两种的判断方式有一点点差别。
3、找到了最长回文字段的中间位置iPos和偏移量iDeviation后，使用substr函数就可以将最长回文字段截取出来。

代码：
函数为：string find_longest_str(const string& Data)

string find_longest_str(const string& Data)
{
	//用于存放子串的字符串
	string child;

	//字符串下标
	int iPos = 0;

	//字符串偏移
	int iDeviation = 0;

	//最长子串
	int imax = 0;

	//当前最长字串
	int iCurent = 0;

	//遍历整个字符串，每个字符都进行中心扩散判断
	for (; iPos < Data.size(); ++iPos)
	{
		//回文子串相邻两位相同时
		if (Data[iPos] == Data[iPos + 1])
		{
			//情况1、偶数位两位开始增加
			iCurent += 2;

			//偏移量每次加1
			++iDeviation;
			while (iPos - iDeviation >= 0 &&
				iPos + iDeviation + 1 < Data.size() &&
				Data[iPos - iDeviation] == Data[iPos + iDeviation + 1])
			{
				iCurent += 2;
				++iDeviation;
			}
			//最大回文子串小于当前回文子串则替换数值
			if (imax < iCurent)
			{
				imax = iCurent;
				child.clear();
				string(child).swap(child);
				child = Data.substr(iPos - iDeviation + 1, imax);
			}
			//下一个字符处，当前长度和偏移量归0
			iCurent = 0;
			iDeviation = 0;
		}

		//默认情况下，回文子串为奇数位
		//奇数位1位开始增加
		iCurent += 1;

		//偏移量每次加1
		++iDeviation;
		while (iPos - iDeviation >= 0 &&
			iPos + iDeviation < Data.size() &&
			Data[iPos - iDeviation] == Data[iPos + iDeviation])
		{
			iCurent += 2;
			++iDeviation;
		}

		//最大回文子串小于当前回文子串则替换数值
		if (imax < iCurent)
		{
			imax = iCurent;
			child.clear();
			string(child).swap(child);
			child = Data.substr(iPos - iDeviation + 1, imax);
		}
		//下一个字符处，当前长度和偏移量归0
		iCurent = 0;
		iDeviation = 0;
	}
	//cout << child << endl;
	return child;
}

//测试函数
void func1()
{
	string str("qweraa6aaaarewq");
	string a = find_longest_str(str);
	cout << a << endl;
}

int main()
{
	func1();
	return 0;
}

运行结果：

成功找到字符串qweraa6aaaarewq中的最长回文字段aa6aa