blocks|key|1619841|text|在实践中它会更快吗？是。对于大-哦，会更快吗？不是的。动态规划解总是O(n*m)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1619842|使用后缀树可能会遇到的问题是，用后缀树的线性时间扫描来换取空间上的巨大损失。后缀树通常比算法的动态编程版本所需实现的表大得多。取决于字符串的长度，动态编程完全可能会更快。|1619843|祝你好运:)|1619844|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Will it be faster in practice? Yes. Will it be faster regarding Big-Oh? No. The dynamic programming solution is always O(n*m).

The problem that you might run into with suffix trees is that you trade the suffix tree's linear time scan for a huge penalty in space. Suffix trees are generally much larger than the table you'd need to implement for a dynamic programming version of the algorithm. Depending on the length of your strings, it's entirely possible that dynamic programming will be faster.

Good luck :)

blocks|key|1338991|text|这将使它运行得更快，尽管它仍然是O(nm)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1338992|一个优化是在空间(这可能为您节省一点分配时间)注意到LCSuff只取决于上一行--因此，如果您只关心长度，可以将O(nm)空间优化到O(min(n,m))。|1338993|这样做的目的是只保留两行--正在处理的当前行和刚刚处理的前一行，并丢弃其余的行。|1338994|entityMap^0|G|5|0|Q|6|1K|5|1U|B|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|O|8|@$9|P|A|Q|B|C]|$9|R|A|S|B|C]|$9|T|A|U|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|V|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|K|$]]

These will make it run faster, though it'll still be <code>O(nm)</code>.

One optimization is in space (which might save you a little allocation time) is noticing that <code>LCSuff</code> only depends on the previous row -- therefore if you only care about the length, you can optimize the <code>O(nm)</code> space down to <code>O(min(n,m))</code>.

The idea is to keep only two rows -- the current row that you are processing, and the previous row that you just processed, and throw away the rest.

blocks|key|1619891|text|迈尔比特矢量算法可以帮你。它通过使用位操作来工作，而且是一种更快的方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1619892|entityMap|0|LINK|mutability|MUTABLE|url|http://www.gersteinlab.org/courses/452/09-spring/pdf/Myers.pdf^0|0|8|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

<a href="http://www.gersteinlab.org/courses/452/09-spring/pdf/Myers.pdf" rel="nofollow">Myer's bit vector algorithm</a> can help you. It works by using bit manipulation and is a much faster approach.

blocks|key|1619905|text|这里有一个简单的算法，可以在O(m%2Bn)+*log(m%2Bn))中完成，与后缀树算法(O(m%2Bn)运行时)相比，实现起来容易得多。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1619906|让它以最小公共长度(minL)+=+0和最大公共长度(maxL)+=+min(m%2Bn)%2B1开始。|1619907|1.+if+(minL+==+maxL+-+1),+the+algorithm+finished+with+common+len+=+minL.

2.+let+L+=+(minL+%2B+maxL)/2

3.+hash+every+substring+of+length+L+in+S,+with+key+=+hash,+val+=+startIndex.

4.+hash+every+substring+of+length+L+in+T,+with+key+=+hash,+val+=+startIndex.+check+if+any+hash+collision+in+to+hashes.+if+yes.+check+whether+whether+they+are+really+common+substring.+

5.+if+there're+really+common+substring+of+length+L,+set+minL+=+L,+otherwise+set+maxL+=+L.+goto+1.|code-block|syntax|javascript|1619908|剩下的问题是如何在时间O(n)中散列长度为L的所有子字符串。您可以使用如下多项式公式：|1619909|Hash(string+s,+offset+i,+length+L)+=+s[i]+*+p%5E(L-1)+%2B+s[i%2B1]+*+p%5E(L-2)+%2B+...+%2B+s[i%2BL-2]+*+p+%2B+s[i%2BL-1];+choose+any+constant+prime+number+p.

then+Hash(s,+i%2B1,+L)+=+Hash(s,+i,+L)+*+p+-+s[i]+*+p%5EL+%2B+s[i%2BL];|1619910|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Here's a simple algorithm which can finishes in O((m+n)*log(m+n)), and much easier to implement compared to suffix tree algorithm which is O(m+n) runtime.

let it start with min common length (minL) = 0, and max common length (maxL) = min(m+n)+1.

<pre><code>1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.
</code></pre>

The remaining problem is how to hash all substring with length L in time O(n). You can use a polynomial formula as follow:

<pre><code>Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];
</code></pre>

I have two very large strings and I am trying to find out their <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem" rel="nofollow noreferrer">Longest Common Substring</a>.

One way is using suffix trees (supposed to have a very good complexity, though a complex implementation), and the another is the dynamic programming method (both are mentioned on the Wikipedia page linked above).

Using dynamic programming
<img src="https://upload.wikimedia.org/math/5/9/b/59bedec58669e638a84364c93529cb4e.png" alt="alt text">

The problem is that the dynamic programming method has a huge running time (complexity is <code>O(n*m)</code>, where <code>n</code> and <code>m</code> are lengths of the two strings).

What I want to know (before jumping to implement suffix trees): Is it possible to speed up the algorithm if I only want to know the length of the common substring (and not the common substring itself)?

How to speed up calculation of length of longest common substring?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有两个非常大的字符串，我正在试图找出它们的。一种方法是使用后缀树(虽然这是一个复杂的实现，但应该具有很好的复杂性)，另一种方法是动态编程方法(这两种方法都在上面链接的维基百科页面中提到)。使用动态规划​问题是动态规划方法有很长的运行时间(复杂性为O(n*m)，其中n和m是两个字符串的长度)。我想知道的(在跳到实现后缀...

问如何加快最长公共子串长度的计算？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何加快最长公共子串长度的计算？EN