草庐IT

java - 查找所有回文子串

coder 2023-05-18 原文

如果输入是 'abba'，那么可能的回文数是 a, b, b, a, bb, abba。
我知道确定字符串是否是回文很容易。就像:

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

但是找到回文子串的有效方法是什么？

最佳答案

这可以在 O(n) 中完成，使用 Manacher's algorithm .

主要思想是动态规划和(正如其他人已经说过的)计算给定字母中心的最大回文长度的组合。

我们真正要计算的是最长回文的半径，而不是长度。 radius 只是 length/2 或 (length - 1)/2(对于奇数长度回文)。

在给定位置 i 计算回文半径 pr 后，我们使用已计算的 radiuses 在 [i - pr 范围内查找回文；我]。这让我们(因为回文是，嗯，回文)跳过对范围 [i 的 radiuses 的进一步计算； i + pr].

当我们在 [i - pr 范围内搜索时； i]，每个位置i - k有四种基本情况(其中k 在 1,2,... pr):

  • 在i - k处没有回文(radius = 0)
    (这也意味着 radius = 0 在 i + k)
  • inner回文，这意味着它适合范围
    (这意味着 i + k 处的 radius 与 i - k 处的相同)
  • outer回文，这意味着它不适合范围
    (这意味着 i + k 处的 radius 被 缩减 以适应范围，即因为 i + k + radius > i + pr 我们将 radius 减少到 pr - k)
  • sticky回文，表示i + k + radius = i + pr
    (在这种情况下，我们需要在 i + k 处搜索可能更大的半径)

完整、详细的解释会相当长。一些代码示例呢？ :)

我找到了波兰老师 Jerzy Wałaszek 先生对该算法的 C++ 实现。
我已将评论翻译成英文，添加了一些其他评论并简化了一些，以便更容易捕获主要部分。
Take a look here .

注意:如果在理解为什么这是 O(n) 时遇到问题，请尝试这样看:
在某个位置找到radius(我们称之为r)后，我们需要遍历r 元素返回，但结果我们可以跳过 r 元素的计算。因此，迭代元素的总数保持不变。

关于java - 查找所有回文子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19801081/

回文javacodeemalgorithmsubstringpalindrome

有关java - 查找所有回文子串的更多相关文章

  1. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  2. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  3. ruby-on-rails - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

  4. ruby - Nokogiri 剥离所有属性 - 2

    我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？ 最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog

  5. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  6. ruby - 获取模块中定义的所有常量的值 - 2

    我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

  7. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  8. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  9. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  10. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

随机推荐