• 数据库
  • Mysql
  • Nosql
  • 技术框架
  • Spring
  • Kafka
  • ibatis
  • 分布式
  • Linux
  • 关于我们
  • 注册
  • 登录
  • 欧宝安德拉-Manacher欧宝安德拉(最长回文子串、回文半径)

    2022-5-5 diaba 欧宝安德拉

    package com.jiucaiyuan.net.question;
    
    /**
     * Manacher欧宝安德拉
     * 解决问题:字符串str中,最长回文子串的长度如何求解?
     * 如何做到时间复杂度O(N)完成?
     *
     * @Author jiucaiyuan  2022/5/2 13:29
     * @mail services@jiucaiyuan.net
     */
    
    public class Manacher {
    
        /**
         * <pre>
         * <b>求输入字符s的最大回文子串(非子序列)</b>
         * <b>Manacher欧宝安德拉</b>(最长回文子串)
         * 【欧宝安德拉中概念】:
         *      R 最右回文边界 (代码中表示回文边界的下一个位置,为了写代码方便)
         *      C 最右回文边界R对应的回文中心位置
         *      L R关于C的对称点
         *      pArr 回文半径数组pArr[],pArr[i]表示以i位置为中心找最大回文,得到的回文半径长度赋值给pArr[i]
         * 【不同情况处理】
         *      1)当前点,没有在最右回文边界R里(在R之外)
         *          暴力破
         *      2)当前点,相对C的对称点i`的回文区域在L和R内部(R相对C点的对称点是L)
         *          这时候i的回文半径和i`的回文半径一样
         *      3)当前点,相对C的对称点i`的回文区域,一部分跑到L的外面
         *          这时候i的回文半径是i到R距离(R-i)
         *      4)当前点,相对C的对称点i`的回文区域,左侧正好压在L上
         *          这时候i的回文半径从R开始,继续向右验证(i到R内不需要验证)
         * </pre>
         *
         * @param s
         * @return
         */
        public static int maxLengthPalindromeSubString(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            char[] str = manacherString(s); //12321 ——> #1#2#3#2#1#
            int[] pArr = new int[str.length]; //回文半径数组,每个字符的回文半径组成的数组   经过下面for代码后,回文半径数组被填充了
            int C = -1;  //最右回文边界R对应的回文中心位置
            int R = -1; //最右回文边界再往右一个位置,最右的有效区是 R-1 位置
            int max = Integer.MIN_VALUE;  //扩出来的最大值
    
            for (int i = 0; i != str.length; i++) {  //每个位置都求回文半径
    
                //如果i在R外,不用验的区域是1
                //如果i在R内,Math.min(pArr[2 * C - i], R - i)        2 * C - i是i`的位置,R-i
                //所以i至少的回文半径区域赋值给pArr[i]
                //i<R  表示i在R内   各种情况不用验的区域都汇聚到此
                pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - i) : 1;
    
                //不用验(是否回文的区域、加速)的区域确定后,并没有超过边界,继续进行尝试
                while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                    //不用验的区域确定后,再尝试往两边验证下是否相同,如果相同,回文半径++
                    if (str[i + pArr[i]] == str[i - pArr[i]]) {
                        pArr[i]++;
                    } else {
                        break;
                    }
                }
    
                //如果扩完发现R可以变大,则记录最大回文半径R及对应的中点C
                if (i + pArr[i] > R) {
                    R = i + pArr[i];
                    C = i;
                }
    
                //记录以每个字符为中心往外扩找最大回文时的最长回文长度
                max = Math.max(max, pArr[i]);
            }
    
            //max是加特殊字符后的回文半径,原始串的回文长度正好等于加特殊字符后的回文半径-1
            return max - 1;
        }
    
        /**
         * 把输入的字符串加工成加入#字符的新字符数组
         * 如:输入"12345",返回['#','1','#','2','#','3','#','4','#','5','#']
         * @param str 原始字符串
         * @return 原始字符串空隙加入特殊字符#后对应的字符数组
         */
        public static char[] manacherString(String str) {
            char[] charArr = str.toCharArray();
            char[] res = new char[str.length() * 2 + 1];
            int index = 0;
            for (int i = 0; i != res.length; i++) {
                res[i] = (i & 1) == 0 ? '#' : charArr[index++];
            }
            return res;
        }
    
        public static void main(String[] args) {
            String str = "abc1234321ab";
            System.out.println(str+"最长回文子串长度="+maxLengthPalindromeSubString(str));
        }
    
    }
    

    发表评论:

  • 最新文章

  • Go-数组,切片,map
  • scp拷贝文件
  • 笔试题-牛羊吃草问题
  • 笔试题-最少的袋子数装苹果
  • 递归DP-找零钱的方法数
  • 存档

  • 2022年10月(1)
  • 2022年8月(1)
  • 2022年6月(11)
  • 2022年5月(6)
  • 2022年4月(33)
  • 2022年3月(26)
  • 2021年3月(1)
  • 2020年9月(2)
  • 2018年8月(1)
  • 2018年3月(1)
  • 2017年3月(3)
  • 2017年2月(6)
  • 2016年12月(3)
  • 2016年11月(2)
  • 2016年10月(1)
  • 2016年9月(3)
  • 2016年8月(4)
  • 2016年7月(3)
  • 2016年6月(4)
  • 2016年5月(7)
  • 2016年4月(9)
  • 2016年3月(4)
  • 2016年2月(5)
  • 2016年1月(17)
  • 2015年12月(15)
  • 2015年11月(12)
  • 2015年10月(6)
  • 2015年9月(11)
  • 2015年8月(8)
  • 分类

  • Java(4)
  • 基础(8)
  • IO(3)
  • JVM(7)
  • 多线程(11)
  • 调优命令(1)
  • Go(0)
  • 基础(1)
  • Linux(10)
  • mac(12)
  • 数据库(2)
  • Mysql(7)
  • Nosql(8)
  • 技术框架(2)
  • Spring(5)
  • Kafka(3)
  • ibatis(2)
  • 分布式(4)
  • 数据结构与欧宝安德拉(0)
  • 数据结构(6)
  • 欧宝安德拉(44)
  • 笔试题(19)
  • emlog(1)
  • 问题解决记录(2)
  • 随笔记录(26)
  • 金融(1)
  • 工具使用(8)
  • 操作系统(3)
  • 用友NC(3)
  • NC常见问题(2)
  • 热门文章

  • SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
  • Mac-删除卸载GlobalProtect
  • java.lang.SecurityException: JCE cannot authenticate the provider BC
  • Idea之支持lombok编译
  • MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
  • 标签

    mac emlog NC授权 授权数 用户数 破解 天上一天 redis 已达授权数 用友NC 可打印 地上一年 超光速 大于光速 时间静止 时光倒流 相对论 go基础 shell CountDownLatch 狱中诗 线程同步 任务同步 SecureCRT 光标消失 做人 做事 职业发展 选人 转义字符 json 格式错误 内存分区 操作系统 cache 分布式 程序 Linux crontab 定时任务 license 安全 备份 IO操作 同步 异步 阻塞 进程 线程 并发 共享内存 mybatis Improper inline 数据库 mysql 如果为null query paxos 分布式一致性 if ifnull spring ioc BlockingQueue OOM 软引用 弱引用 并行 jvm参数 gc jvm kafka 2016 数据库引擎 加密 解密 java文件压缩 命令 RDB AOF 配置 调优 sharding jvm结构 存储引擎 myiasm innodb 乐观锁 悲观锁 理财 欧宝安德拉 异地多活 ctrl+alt+delete idea lombok springmvc aes 宝宝 项目经理 nc curl 按位操作 逻辑思维 excel 原子增操作 awk printf OceanBase mac锁屏 快捷键 文件监听 confict git 商品管理 sku 自动注入 Apple ID Javassist branch 正则表达式 参数必填 代码优化 grep 程序员 未来 保险 坦然生活 抗风险 优秀经纪人 汉诺塔 递归
  • 最新评论

  • logisqykyk
    Javassist分析、编辑和创建jav...
  • xxedgtb
    Redis—常见参数配置 - 韭菜园 ...
  • wdgpjxydo
    SpringMVC:Null Model...
  • rllzzwocp
    Mysql存储引擎MyISAM和Inno...
  • dpkgmbfjh
    SpringMVC:Null Model...
  • tzklbzpj
    SpringMVC:Null Model...
  • bqwrhszmo
    MyBatis-Improper inl...
  • 乐谱吧
    good非常好
  • diaba
    @diaba:应该说是“时间的度量依据”...
  • diaba
    如果速度增加接近光速、等于光速、甚至大于...
  • 最新微语

  • 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界

    2022-03-21 23:31

  • 2022.03.02 23:37:59

    2022-03-02 23:38

  • 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!

    2018-07-18 10:49

  • 2018年关键字“走心”

    2018-03-19 16:07

  • 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!

    2017-12-20 10:24

  • 更多»

    Powered by emlog 京ICP备15045175号-1 Copyright © 2022