字符串后面补最短长度的字符,使其整体成回文字符串(java)

这篇具有很好参考价值的文章主要介绍了字符串后面补最短长度的字符,使其整体成回文字符串(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

补齐字符串使其成为回文字符串

给定一个字符串str,只能在str的后面添加字符,想让str整体变成回文串,返回至少要添加几个字符

Manacher 算法

首先介绍下manacher 算法:
Manacher 算法是一种线性时间复杂度的求解最长回文子串的算法。它的核心思想是利用已知回文信息,避免重复计算。 Manacher 算法的基本思想是通过预处理得到一个包含原字符串所有回文子串的数组,然后对于每个字符,如果它是回文中心,则将它的位置加倍,否则不做任何修改。最后返回数组中最大的值即可 。具体可以看下上期manacher算法。
Manacher算法 – 回文长度算法
可以先看上期的回文字符串的算法,这个可以在时间复杂度为O(n)的情况下,计算出最长回文子串的长度。

在这个题中,我们只需要找到第一次半径到字符串末尾的字符位置,然后补齐前面到半径位置的字符,就是需要的最短的字符串。
举个例子:
123abcbabc 在这个字符串中,用manacher 算法中,找到第一次回文半径到字符末尾的位置字符,也就是倒数一个a的位置,然后补齐以a为只心的回文字符前面的字符,也就是ba321.使其整体成为回文字符串。

代码演示

/**
     * 补齐字符串。
     * @param s
     * @return
     */
    public static String shortestEnd(String s) {
        //只有一个字符串时,不需要补
        if (s == null || s.length() < 2){
            return null;
        }

        char[] chars = manacherString(s);
        int[] pArr = new int[chars.length];
        int C = 0;
        int R = 0;
        int maxContainsEnd = -1;

        for (int i = 0;i < chars.length;i++){
            pArr[i] = R > i ? Math.min(pArr[2 * C - i],R - i) : 1;

            while (i + pArr[i] < chars.length && i - pArr[i] > -1){
                if (chars[i + pArr[i]] == chars[i - pArr[i]]){
                    pArr[i]++;
                }else {
                    break;
                }
            }
            if (i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }
            if (R == chars.length){
                maxContainsEnd = pArr[i];
                break;
            }
        }

        char[] ans = new char[s.length() - maxContainsEnd + 1];
        for (int i = 0; i < ans.length;i++){
            ans[ans.length - i -1] = chars[i * 2 + 1];
        }
        return new String(ans);
    }


        /**
         * 处理字符串
         * @param s
         * @return
         */
    public static char[] manacherString(String s){
        char[] chars = s.toCharArray();
        char[] res = new char[chars.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length;i++){
            res[i] = (i & 1) == 0 ? '#' : chars[index++];
        }
        return res;
    }

Manacher 算法

Manacher算法 – 回文长度算法文章来源地址https://www.toymoban.com/news/detail-564446.html

到了这里,关于字符串后面补最短长度的字符,使其整体成回文字符串(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 字符串(字节)长度计算

    字节(Byte)是计算机信息技术用于计量存储容量的一种计量单位,也表示一些计算机编程语言中的数据类型和语言字符。 一个字节(byte)8位(bit),十进制表示0~255。 两个字节16位,可表示十进制0~65535。 Unicode 做了一件事,就是给世界上所有字符都分配了一个唯一的数

    2024年02月05日
    浏览(61)
  • C语言:写一个函数,求字符串的长度,在main函数中输入字符串并输出其长度(指针)

    分析:    在程序中,定义一个函数 fix,该函数使用指针变量来访问字符串中的每个字符,并计算出字符串的长度。fix 函数的参数为指向 char 类型的指针变量 p,表示需要计算长度的字符串。   在主函数 main 中,定义一个大小为 20 的字符数组 a,用于存储输入的字符串。然

    2024年01月21日
    浏览(74)
  • C++ 字符串长度计算

    C++常用的长度计算方法size()、sizeof() 、strlen()、length() size():计算长度,std::string类的成员函数 length():计算长度,std::string类的成员函数 sizeof():计算所占用空间的字节数,是运算符;在编译时计算,获得保证能容纳实现所建立的最大对象的字节大小,因此sizeof不能用来返回

    2024年02月11日
    浏览(62)
  • C/C++字符函数和字符串函数详解————长度受限制的字符串函数

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言         2.长度受限制的字符串函数 2.1strncpy函数 2.2strncat函数 2.3strncmp函数

    2024年02月08日
    浏览(64)
  • Python计算字符串长度的函数

    1、使用内置函数len 这是Python中一种常用的函数,主要功能就是对字符串的长度进行统计,最后会返回一个字符串的实际长度,使用方法如下: 在示例中str就是一个要计算的字符串,它还可以是列表或者是字典等等。 2、使用for循环 使用for循环来统计字符串的长度时,我们可以

    2024年02月13日
    浏览(52)
  • java中压缩字符串的长度

    在 Java 中,可以使用压缩算法对字符串进行压缩,以减少字符串的长度。常见的压缩算法包括 Gzip、Deflate 和 Bzip2 等。 下面是一个使用 Gzip 压缩算法对字符串进行压缩的示例代码: 在这个示例代码中,我们首先定义了一个需要压缩的字符串 originalString 。然后,我们使用 Gzi

    2024年02月16日
    浏览(40)
  • Java如何求得字符串的长度

    在 Java 中,要获取字符串的长度,可以使用 String 类的 length() 方法 其语法格式: 字符串名.length(); 返回的值是int类型的长度值。 举例: 1.例如现在接收到了一串字符串,可能接收到的是正常的字符串,也有可能是空字符串,这时候就需要判断下字符串是否存在值,就可以使

    2024年02月16日
    浏览(51)
  • LeetCode——最小化字符串长度

    目录 一、题目 二、题目解读  三、代码  1、set去重 2、用一个二进制数记录每个字母是否出现过 6462. 最小化字符串长度 - 力扣(Leetcode) 给你一个下标从  0  开始的字符串  s  ,重复执行下述操作  任意  次: 在字符串中选出一个下标  i  ,并使  c  为字符串下标  i

    2024年02月08日
    浏览(58)
  • 【Python系列】获取字符串的长度

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年04月09日
    浏览(49)
  • Java格式化字符串输出固定长度,不够长度空格补全长度

    字串格式化输出经常用到,将字串固定输出长度可以使用如下方式格式化输出: 输出结果: 你好              length16 %-16s :表示输出固定长度16为,如源字串长度不足16位,-表示右侧补空格至16位; 同样,如果想实现固定输出长度16位,长度不足左侧补空格,可使用%16s。

    2024年02月08日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包