给定一个字符串S，我想找出是否存在不重叠的子串A、B和C 在 S 中，因此当子字符串被解释为十进制数时，等式 A + B = C 成立。
示例:对于 S = 17512，答案是肯定的，因为 12 + 5 = 17 成立。
这不是作业题，我已经尝试过构建后缀数组来解决这个问题
17512
7512
512
12
2
但后来我意识到给定 132，1 + 2 = 3 在选择时是否需要其他形式的排列？
如何有效地解决这个问题？
最佳答案
令 S 为数字的十进制表示。如果 n = |S| 足够小(<500>
让我们从等式 A + B = C 中枚举 A 和 C(我们假设 w.l.o.g. A > B)。我们知道它们的大小必须大致相同(加/减一位数)，因此枚举可能性是一次三次运算(有 O(n3)候选人)。
对于每个候选对 (A, C)，我们需要检查 B = C - A 是否在字符串中并且不与任何 重叠>A 或 C 子串。我们可以使用以 10 为基数的算术计算线性时间的差异。
棘手的部分是检查B 是否是不与A 或C 重叠的子串。 A 和 C 将字符串分成 3 部分:
S = xAyCz
如果我们以一种巧妙的方式枚举它们，固定起始位置并减小大小，我们可以维护 suffix automata部分 x 和部分 y 和 z 的反面。
现在我们可以在线性时间内检查 B = C - A(或其相反)是否存在于这三个部分之一中。
这种方法的时间复杂度:Θ(n4)。
这里有一个变体，稍微复杂一些，但速度更快(感谢 Evgeny 指出):
运行时间:O(n3 log n)。
更新:关于需要使用所有字符的简化版本:
我们首先意识到，如果我们以 10 为基数，我们可以在线性时间内对字符串的子串进行算术运算。
现在我们要找到 split 点a <>，这样你的三个子串就是A = s1...sa ，B = sa+1...sb 和C = sb+1...sn.
我们可以证明a 和b 的候选数只有常数，因为这三个部分的大小必须大致相同，方程才能成立。
使用任意精度算法，我们可以轻松地尝试所有候选对 (a,b) 并针对每个候选对找到 M = max(A,B,C)。然后检查 M 是否是其他两个数字的总和。
总时间复杂度:Θ(n)。
关于java - 给定一个数字检查数字是否形成加法方程？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22463777/
给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru
使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta
我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何
我想要做的是有2个不同的Controller，client和test_client。客户端Controller已经构建，我想创建一个test_clientController，我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集，然后呈现客户端Controller的索引View，以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>
为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar
这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife
我不确定传递给方法的对象的类型是否正确。我可能会将一个字符串传递给一个只能处理整数的函数。某种运行时保证怎么样？我看不到比以下更好的选择:defsomeFixNumMangler(input)raise"wrongtype:integerrequired"unlessinput.class==FixNumother_stuffend有更好的选择吗？ 最佳答案 使用Kernel#Integer在使用之前转换输入的方法。当无法以任何合理的方式将输入转换为整数时，它将引发ArgumentError。defmy_method(number)
如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象
关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/