几种回文算法的比较

前言

这是我的第一篇博文，献给算法。

学习和研究算法可以让人变得更加聪明。

算法的目标是以更好的方法完成任务。

更好的方法的具体指标是:

  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--;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 循环结束时d总不满足判断条件，所以减1
        if (2 * d + 1 > l_max){
            max   = i - d;
            l_max = 2 * 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--;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// 循环结束时d总不满足判断条件，所以减1
        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)算法

马拉车算法使用空间换取时间，把每个点的回文半径存储起来。为了避免轮询两次，算法把原始文本的每个字符让固定字符(比如#)前后包围起来，这样，对于原始文本aba和abba，处理后的文本变成#a#b#a#和#a#b#b#a#，这样，无论对于#a#b#a#和#a#b#b#a#，总有中心对称点m。

算法把回文半径存储起来，在一个已经确定的大的回文当中，右半部分的点的回文与已经确定的左边部分的点回文具有对称性，所以节省掉一部分轮询的时间。这里说的某点的回文，指以该点为中心对称的回文。

 

 如上图，以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的指令呢。

如果有大侠路过，请赐教。