查找字符串中最长的重复序列 - python

我需要在字符串中找到最长的序列,但要注意,该序列必须重复三次或更多次。因此,例如,如果我的字符串是:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

那么我想返回值“ helloworld ”。

我知道完成此操作的几种方法,但是我面临的问题是实际的字符串非常大,因此我确实在寻找一种可以及时实现的方法。

参考方案

这个问题是longest repeated substring problem的变体,并且存在一个使用suffix trees的O(n)时间算法来解决它。这个想法(如Wikipedia所建议)是构造后缀树(时间O(n)),用后代数注释树中的所有节点(使用DFS的时间O(n)),然后找到树中具有至少三个后代的最深节点(使用DFS的时间O(n))。该总体算法花费时间O(n)。

就是说,众所周知,后缀树很难构造,因此您可能想在尝试实现后找到一个为您实现后缀树的Python库。快速的Google搜索会显示this library,尽管我不确定这是否是一个很好的实现。

另一种选择是将suffix arrays与LCP arrays结合使用。您可以遍历LCP阵列中的相邻元素对,并取每对中的最小值,并存储以此方式找到的最大元素数。这将对应于最长重复至少三次的字符串的长度,然后您可以从那里读取字符串本身。

有几种用于构建后缀数组的简单算法(Manber-Myers算法在时间O(n log n)上运行,不太难编写代码),Kasai的算法在时间O(n)上构建LCP数组,这相当合理。直接编写代码。

希望这可以帮助!

用大写字母拆分字符串,但忽略AAA Python Regex - python

我的正则表达式:vendor = "MyNameIsJoe. I'mWorkerInAAAinc." ven = re.split(r'(?<=[a-z])[A-Z]|[A-Z](?=[a-z])', vendor) 以大写字母分割字符串,例如:'我的名字是乔。 I'mWorkerInAAAinc”变成…

Python GPU资源利用 - python

我有一个Python脚本在某些深度学习模型上运行推理。有什么办法可以找出GPU资源的利用率水平?例如,使用着色器,float16乘法器等。我似乎在网上找不到太多有关这些GPU资源的文档。谢谢! 参考方案 您可以尝试在像Renderdoc这样的GPU分析器中运行pyxthon应用程序。它将分析您的跑步情况。您将能够获得有关已使用资源,已用缓冲区,不同渲染状态上…

Python:图像处理可产生皱纹纸效果 - python

也许很难描述我的问题。我正在寻找Python中的算法,以在带有某些文本的白色图像上创建皱纹纸效果。我的第一个尝试是在带有文字的图像上添加一些真实的皱纹纸图像(具有透明度)。看起来不错,但副作用是文本没有真正起皱。所以我正在寻找更好的解决方案,有什么想法吗?谢谢 参考方案 除了使用透明性之外,假设您有两张相同尺寸的图像,一张在皱纹纸上明亮,一张在白色背景上有深…

Python uuid4,如何限制唯一字符的长度 - python

在Python中,我正在使用uuid4()方法创建唯一的字符集。但是我找不到将其限制为10或8个字符的方法。有什么办法吗?uuid4()ffc69c1b-9d87-4c19-8dac-c09ca857e3fc谢谢。 参考方案 尝试:x = uuid4() str(x)[:8] 输出:"ffc69c1b" Is there a way to…

Python sqlite3数据库已锁定 - python

我在Windows上使用Python 3和sqlite3。我正在开发一个使用数据库存储联系人的小型应用程序。我注意到,如果应用程序被强制关闭(通过错误或通过任务管理器结束),则会收到sqlite3错误(sqlite3.OperationalError:数据库已锁定)。我想这是因为在应用程序关闭之前,我没有正确关闭数据库连接。我已经试过了: connectio…