为什么 c++ 实现的 string::find() 不使用 KMP algorithm (并且不在 O(N + M) 中运行)并在 O(N * M) 中运行？这在 C++0x 中是否得到纠正？
如果当前查找的复杂度不是O(N * M)，那是什么？
那么 gcc 中实现了什么算法呢？是KMP吗？如果不是，为什么？
我已经测试过了，运行时间显示它运行在 O(N * M)
最佳答案
Why the c++'s implemented string::substr() doesn't use the KMP algorithm (and doesn't run in O(N + M)) and runs in O(N * M)?
我假设您的意思是 find()，而不是 substr()，它不需要搜索并且应该在线性时间内运行(并且只是因为它必须将结果复制到一个新字符串中)。
C++ 标准没有指定实现细节，仅在某些情况下指定复杂性要求。 std::string 操作的唯一复杂性要求是 size()、max_size()、operator[]、swap()、c_str()和data()都是常数时间。其他任何事情的复杂性取决于实现您正在使用的库的人所做的选择。
选择简单搜索而不是 KMP 之类的最可能的原因是避免需要额外的存储空间。除非要找到的字符串很长，并且要搜索的字符串包含很多部分匹配，否则分配和释放所花费的时间可能会远远超过额外复杂性的成本。
Is that corrected in c++0x?
不，C++11 没有对 std::string 增加任何复杂性要求，当然也没有增加任何强制性的实现细节。
If the complexity of current substr is not O(N * M), what is that?
这是最坏情况的复杂性，当要搜索的字符串包含很多长的部分匹配时。如果字符具有合理均匀的分布，则平均复杂度将更接近 O(N)。因此，通过选择具有更好的最坏情况复杂性的算法，您可能会使更典型的情况变得更慢。
关于C++ string::find 复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8869605/
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
对于作为String#tr参数的单引号字符串文字中反斜杠的转义状态，我觉得有些神秘。你能解释一下下面三个例子之间的对比吗？我特别不明白第二个。为了避免复杂化，我在这里使用了'd'，在双引号中转义时不会改变含义("\d"="d")。'\\'.tr('\\','x')#=>"x"'\\'.tr('\\d','x')#=>"\\"'\\'.tr('\\\d','x')#=>"x" 最佳答案 在tr中转义tr的第一个参数非常类似于正则表达式中的括号字符分组。您可以在表达式的开头使用^来否定匹配(替换任何不匹配的内容)并使用例如a-f来匹配一
在Ruby1.9.3(可能还有更早的版本，不确定)中，我试图弄清楚为什么Ruby的String#split方法会给我某些结果。我得到的结果似乎与我的预期相反。这是一个例子:"abcabc".split("b")#=>["a","ca","c"]"abcabc".split("a")#=>["","bc","bc"]"abcabc".split("c")#=>["ab","ab"]在这里，第一个示例返回的正是我所期望的。但在第二个示例中，我很困惑为什么#split返回零长度字符串作为返回数组的第一个值。这是什么原因呢？这是我所期望的:"abcabc".split("a")#=>["bc"
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
有几种方法:first_or_create_by、find_or_create_by等，它们的工作原理是:与数据库对话以尝试找到我们想要的东西如果我们找不到，就自己做保存到数据库显然，并发调用这些方法可能会使两个线程都找不到它们想要的东西，并且在第3步中一个线程会意外失败。似乎更好的解决方案是，创建或查找即:提前在您的数据库中创建合理的唯一性约束。如果你想保存一些东西，就保存它如果有效，那就太好了。如果它因为RecordNotUnique异常而无法工作，它已经存在，太好了，加载它那么在什么情况下我想使用Rails内置的东西而不是我自己的(看起来更可靠)create_or_find？
我在加密来self正在使用的第三方供应商的值时遇到问题。他们的指令如下:1)Converttheencryptionpasswordtoabytearray.2)Convertthevaluetobeencryptedtoabytearray.3)Theentirelengthofthearrayisinsertedasthefirstfourbytesontothefrontofthefirstblockoftheresultantbytearraybeforeencryption.4)EncryptthevalueusingAESwith:1.256-bitkeysize,2.25
我正在开发西洋跳棋实现，其中有许多易于测试的方法，但我不确定如何测试我的主要#play_game方法。我的大多数方法都可以很容易地确定输入和输出，因此也很容易测试，但这种方法是多方面的，实际上并没有容易辨别的输出。这是代码:defplay_gameputs@gui.introwhile(game_over?==false)message=nil@gui.render_board(@board)@gui.move_requestplayer_input=getscoordinates=UserInput.translate_move_request_to_coordinates(play
方法应返回-1,0或1分别表示“小于”、“等于”和“大于”。对于某些类型的可排序对象，通常将排序顺序基于多个属性。以下是可行的，但我认为它看起来很笨拙:classLeagueStatsattr_accessor:points,:goal_diffdefinitializepts,gd@points=pts@goal_diff=gdenddefothercompare_pts=pointsother.pointsreturncompare_ptsunlesscompare_pts==0goal_diffother.goal_diffendend尝试一下:[LeagueStats.new(
我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“
