前言
这是我的第一篇博文，献给算法。
学习和研究算法可以让人变得更加聪明。
算法的目标是以更好的方法完成任务。
更好的方法的具体指标是:
1. 花费更少的执行时间。
2. 花费更少的内存。
在对方法的不断寻找，对规律的不断探索中，个人的思考能力能够被加强。当快捷的思考能力成为一种固有特征时，人就变得聪明起来。
研究算法其实是研究事物的规律。对事物的变化规律掌握的越准确、越细致、越深入，就能找到更好的算法。
在探索的过程当中，一定会经历失败。但是这种失败是值得的，它为解决其它问题提供了基础。
回文算法:
回文指从左往右和从由往左读到相同内容的文字。比如: aba，abba，level。
回文具有对称性。
回文算法的目标是把最长的回文从任意长度的文本当中寻找出来。比如：从123levelabc中寻找出level。
框架代码
框架代码包含除核心算法代码的所有其他部分代码。
1. main()函数，使用随机数产生1M长度的字符串。然后调用核心算法代码。
2. 运行时间统计函数，用于比较不同算法耗时的差别。
#include <vector> #include <iostream> #include <string> #include <minmax.h> #include <time.h> #include <Windows.h> #include <random> #include <assert.h> using namespace std; __int64 get_local_ft_time(){ SYSTEMTIME st; __int64 ft; GetLocalTime(&st); SystemTimeToFileTime(&st, (LPFILETIME) &ft); return ft; } int diff_ft_time_ms(__int64 subtracted, __int64 subtraction){ return (int)((subtracted - subtraction) / 10000); } int main() { string s = ""; srand(time(NULL)); for (int i = 0; i < 1024 * 1024; i++){ s += (char) ((rand() % 26) + ‘a‘); } // 此处调用回文算法函数。 //cin.get(); }
回文算法: 原始算法
原始算法指按照回文的原始定义，利用数据的对称性(s[i - x] = s[i + x])来寻找回文的算法。
void palindrome_raw(string t) { cout << "palindrome_raw" << endl; __int64 start = get_local_ft_time(); int max = 0; // 最长回文的起点 int l_max = 1; // 最长回文的长度(l: length, 长度的意思) for (int i = 1; i < t.size(); i++) { // i为对称点 int d = 1; // d为回文扩展半径 while (i - d >= 0 && i + d < t.size() && t[i - d] == t[i + d]){ // 以i为中心对称。aba d++; } d--; if (2 * d + 1 > l_max){ max = i - d; l_max = 2 * d + 1; } // 循环结束时d总不满足判断条件，所以减1 d = 0; // d为回文扩展半径 while (i - d >= 0 && i + 1 + d < t.size() && t[i - d] == t[i + 1 + d]){ // 以i后面空隙为中心对称。abba d++; } d--; if (2 * (d + 1) > l_max){ max = i - d; l_max = 2 * (d + 1); } } cout << t.substr(max, l_max) << " " << max << endl; __int64 end = get_local_ft_time(); cout << "处理时间: " << diff_ft_time_ms(end, start) << "ms" << endl; }
算法说明:
对每个数据位置i, 分别寻找
1. 以i为对称点的回文。比如文本: aba，以b对称。
2. 以i与i+1直接的空隙对称的回文。比如文本abba，以bb之间的空隙对称。
所以，对每个点，轮询两次。
回文算法: 马拉车(Manacher)算法
马拉车算法使用空间换取时间，把每个点的回文半径存储起来。为了避免轮询两次，算法把原始文本的每个字符让固定字符(比如#)前后包围起来，这样，对于原始文本abcd，处理后的文本变成#a#b#c#d#。
算法把回文半径存储起来，在一个已经确定大的回文当中，右半部分的数据的回文与已经确定的左边部分的回文具有对称性，所以节省掉一部分轮询的时间。
如上图，m点的回文半径已经确定是p[m]，那么对于m点右侧的i点，总有一个沿m点对称的j点。由于m点回文的对称性，j点的回文与i点的回文在m回文的区域是一定对称的。这是马拉车算法规律的基础。
代码直接引用自: https://www.cnblogs.com/grandyang/p/4475985.html
void Manacher(string s) { cout << "Manacher" << endl; // Insert ‘#‘ string t = "$#"; for (int i = 0; i < s.size(); ++i) { t += s[i]; t += "#"; } // Process t vector<int> p(t.size(), 0); __int64 start = get_local_ft_time(); int mx = 0, id = 0, resLen = 0, resCenter = 0; for (int i = 1; i < t.size(); ++i) { p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; while (t[i + p[i]] == t[i - p[i]]) ++p[i]; if (mx < i + p[i]) { mx = i + p[i]; id = i; } if (resLen < p[i]) { resLen = p[i]; resCenter = i; } } cout << s.substr((resCenter - resLen) / 2, resLen - 1) << " " << (resCenter - resLen) / 2 << endl; __int64 end = get_local_ft_time(); cout << "处理时间: " << diff_ft_time_ms(end, start) << "ms" << endl; }
回文算法: 自己尝试的算法
把文本数据看做函数曲线，则有下面的规律：
1. 递增或者递减的区间内，一定没有对称性。
2. 恒值区间，一定有对称性。
3. 递增、递减的属性变化时，在最高点或最低点(拐点)，可能存在对称性。
4. 递增或者递减变化成恒值时，一定没有对称性。
根据以上的规律，写出相应的代码：
void palindrome_zjs(string t) { cout << "palindrome_zjs" << endl; __int64 start = get_local_ft_time(); int l = 0; // 起点l(left，左边的意思) int s = 0; // 符号s(sign, 符号的意思)，代表上升，下降或者平坦 (1, -1, 0) int max = 0; // 最长回文的起点 int l_max = 1; // 最长回文的长度(l: length, 长度的意思) for (int r = 1; r < t.size(); r++) { // 终点r(right, 右边的意思) int s_n = t[r] - t[r - 1]; // 与前面一个点比较 if (s_n){ s_n = s_n > 0 ? 1 : -1; // 上升、下降或者不变? } if (s_n == s) { // 处在递增、递减或者恒值的阶段中，此时不作处理 ; } else if(s_n == 0){ // 由递增、递减变成不变 l = r - 1; // 新线段的起点 s = s_n; // 增减属性 } else if (s == 0) { // 不变的区域结束。恒值区总是自对称，比如aa, aaa int i = 1; int right = r - 1; // right指向最后一个恒值区的位置 while (l - i >= 0 && right + i < t.size() && t[l - i] == t[right + i]){ // 沿恒值区向左右扩展即可。 i++; } i--; // 循环结束时i总不满足判断条件，所以减1 if (right + i - (l - i) + 1 > l_max){ max = l - i; l_max = right + i - max + 1; } l = r; // 新线段的起点 s = s_n; // 增减属性 } else if (s_n != 0) { // 递增变成递减，或者递减变成递增 int i = 1; int c = r - 1; // c是拐点(最低或者最高点)。 while (c - i >= 0 && c + i < t.size() && t[c - i] == t[c + i]){ // 拐点为对称点。 i++; } i--; // i总不满足条件，所以减1 if (2 * i + 1 > l_max){ max = c - i; l_max = 2 * i + 1; // + 1是加拐点本身 } l = r; // 新线段的起点 s = s_n; // 增减属性 } assert(1); } cout << t.substr(max, l_max) << " " << max << endl; __int64 end = get_local_ft_time(); cout << "处理时间: " << diff_ft_time_ms(end, start) << "ms" << endl; }
几种算法的比较
算法 格外的内存 运算时间(1M字节的随机文本)
原始算法 不需要 400ms
马拉车算法 2倍的文本 1311ms
自己的代码 不需要 300ms
结果让人费解，为什么马拉车算法如此耗时?
如果马拉车算法又耗内存又耗时间，使用这种算法的意义在哪里呢？
如果马拉车算法的时间级数为O(n)，那么1M个循环，其运行时间应在在us级才对。粗略地说，1秒可以出来1M*1M的指令呢。
如果有大侠路过，请赐教。
原文：https://www.cnblogs.com/zjsxdmif/p/10113435.html