四种方法获取的最长“回文串”,并对其时间复杂进行分析与对比

 2018-12-26 22:57:58   {{zan}}   0   286 

四种方法获取的最长“回文串”,并对其时间复杂进行分析与对比

题目描述:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。本文中主要是用PHP语言来实现的四种算法,并对其时间复杂进行分析与对比。

实现思路:本文中主要是用PHP语言来实现的四种算法:

        1、暴力破解:暴力计算出所有的字符串并判断。

             时间复杂度:O(n^3)。

        2、移动中心法:先假设某个位置为回文字符串的中心,然后查询以此位中心的最长回文字符串。遍历中心,即可找到全局最长子串。

              时间复杂度:O(n^2)。

        3、公共字符串法:利用公共最长字符串,

              时间复杂度:O(n^2)。

              ps:方法getLongestSameStr(),在我的这篇文章里:求两个字符串的最长公共字符串

        4、Manacher算法:经典的Manacher 算法,优势在于避免了算法②奇偶数讨论的问题,简化了算法②边界判断,还记录了当前字符串的“回文状态”,利用之前的回文状态来求当前回文状态 ,体现了算法③动态规划的思想,存储数据,不用再次计算。        

              时间复杂度:O(n)。

代码实现: 

1、暴力破解

//1.  判断字符串是否是回文字符串
function isPalindrome($str)
{
    if ($str === strrev($str)) {
        return 1;
    } else {
        return 0;
    }
}
//2. 获取一个字符串有多少子串,设置了子串长度最小为2
function getAllSubstring($str)
{
    $all_str_arr = [];
    for ($i = 0; $i < strlen($str); $i++) {
        for ($j = 0; $j < strlen($str) - $i + 1; $j++) {
            if (strlen(substr($str, $i, $j)) > 1) {
                $all_str_arr[] = substr($str, $i, $j);
            }
        }
    }
    return $all_str_arr;
}
//3. 获取一维数组中,元素长度最长的一组
function getArrMaxStr($arr)
{
    $max = 0;
    foreach ($arr as $k => $v) {
        if (strlen($arr[$max]) < strlen($v)) {
            $max = $k;
        }
    }
    return $arr[$max];
}
//4. 取得字符串中,最长的回文串
function getMaxPalindrome1($str)
{
    if (isPalindrome($str)) {
        return $str;
    } else {
        // 拆分成多个字符串,然后循环比较
        foreach (getAllSubstring($str) as $k => $v) {
            if (isPalindrome($v)) {
                $max_str[] = $v;
            }
        }
        return getArrMaxStr($max_str);
    }
}


        以上四个步骤就是获取字符串中最长的回文串,但是这个算法只适合较短的字符串,由上大家也可以看出,步骤2中求每一个子串时间复杂度O(N^2),步骤4中,再循环判断子串是不是回文串O(N),两者是相乘关系,所以时间复杂度为O(N^3)。

暴力求解的优化:

        每次判断一个字符串是否是回文字符串时,将每次的判断结果存存起来,之后再用就不用重新计算了。但需要从后向前遍历,这样才会用得到提前存储的结果。时间复杂度为O(n^2)。(这里就不代码说明了)

2、移动中心法

function getMaxPalindrome2($str)
{
    if (is($str)) {
        return $str;
    } else {
        $len = strlen($str);
        // 假如得到的回文串 为 偶数,abba,即中点是空隙
        $max_str = '';
        $max_arr = [];
        for ($i = 0; $i < $len; $i++) {
            $left = $i;
            $right = $i + 1;
            while ($right < $len && $left >= 0 && $str[$left] == $str[$right]) {
                if (strlen($max_str) <= $right - $left + 1) {
                    $max_str = substr($str, $left, $right - $left + 1);
                    if (is($max_str)) {
                        $max_arr[] = $max_str;
                    }
                }
                $left--;
                $right++;
            }
        }
        // 假如得到的回文串 为 奇数,aba,即中点是字符
        for ($i = 0; $i < $len; $i++) {
            $left = $i - 1;
            $right = $i + 1;
            while ($right < $len && $left >= 0 && $str[$left] == $str[$right]) {
                if (strlen($max_str) <= $right + 1 - $left) {
                    $max_str = substr($str, $left, $right - $left + 1);
                    if (is($max_str)) {
                        $max_arr[] = $max_str;
                    }
                }
                $left--;
                $right++;
            }
        }
        // 两个合成一个的话,就是,只有当奇数回文串的大于或等于偶数回文串的时候,
        $longest_str = [];
        foreach ($max_arr as $v) {
            if (strlen($max_str) == strlen($v)) {
                $longest_str[] = $v;
            }
        }
        return $longest_str;
    }
}
// 判断字符串是否是回文字符串
function isPalindrome($str)
{
    if ($str === strrev($str)) {
        return 1;
    } else {
        return 0;
    }
}

3、公共字符串法

function getMaxPalindrome3($str)
{
    //1. 判断是不是回文
    if (is($str)) return $str;
    //2. 利用最长公共字符串的方法求
    $arr = getLongestSameStr($str, strrev($str));
    return $arr;
}
// 判断字符串是否是回文字符串
function isPalindrome($str)
{
    if ($str === strrev($str)) {
        return 1;
    } else {
        return 0;
    }
}

ps:方法getLongestSameStr(),在我的这篇文章里:求两个字符串的最长公共字符串

4、Manacher算法

function getMaxPalindrome4($str)
{
    // 初始化最大回文序列中间坐标
    $maxxy = 0;
    // 初始化最大回文长度
    $maxLength = 0;
    // 初始化一个空数组存储每次的回文序列中间坐标(key)和回文长度(value)
    $arr = [];
    // 通过在每个字符的两边都插入一个特殊的符号,将所有的回文子串都转换成奇数长度;
    // 在字符串的开始和结尾加入另一个特殊字符,这样就不用特殊处理越界问题
    $newStr = "^#" . implode("#", str_split($str)) . "#\0";
    // 递推,每次取一个数作为中间坐标
    for ($i = 2; $newStr[$i] != "\0"; $i++) {
        // 每个中间坐标的初始回文长度为1
        $arr[$i] = 1;
        // 根据每个中间坐标往两头匹配是否相等
        while ($newStr[$i - $arr[$i]] == $newStr[$i + $arr[$i]]) {
            // 每匹配成功一次,则当前坐标的最大回文长度加一
            $arr[$i]++;
        }
        // 判断当前回文长度是否大于最大的回文长度,大于则进去if代码块更新最大回文次数和更新最大回文中间坐标
        if ($arr[$i] > $maxLength) {
            $maxLength = $arr[$i];//字符串的长度
            $maxxy = $i;//字符串的末位置坐标
 
        }
    }
    // 截取最大回文长度的字符串
 
    $res = substr($newStr, $maxxy - $maxLength + 1, $maxLength * 2 - 1);
    // 清除开始加入的字符并返回
    return str_replace('#', "", $res);
}

最后总结:  

        由上可以清晰看出,时间复杂度④>③=②>①,算法四是最优方案。


欢迎指导!

千而の大狮子!

本文链接地址,转载请标注:https://caohongyuan.cn/article/76

(邮箱不会公开,只会做回复通知用) 提交 清空 {{comment.content}}
Re:{{response.content}}