相关疑难解决方法(0)

我想知道我什么时候做的事情

a = "This could be a very large string..."
b = a[:10]

创建一个新字符串或返回一个视图/迭代器

是否有任何算法可用于查找字符串中最常见的短语(或子串)？例如,以下字符串将"hello world"作为其最常见的双字短语:

"hello world this is hello world. hello world repeats three times in this string!"

在上面的字符串中,最常见的字符串(在空字符串字符之后,重复无限次数)将是空格字符.

有没有办法在这个字符串中生成一个公共子串列表,从最常见到最不常见？

切片Python字符串的时间复杂度是多少？鉴于Python字符串是不可变的,我可以想象将它们切片为O(1)或者O(n)取决于切片的实现方式.

我需要编写一个迭代一个(可能很大)字符串的所有后缀的函数.我可以通过将后缀表示为整个字符串的元组加上一个开始读取字符的索引来避免切片,但这很难看.如果相反,我天真地写这样的函数:

def do_something_on_all_suffixes(big_string):
    for i in range(len(big_string)):
        suffix = big_string[i:]
        some_constant_time_operation(suffix)

... ...将其时间复杂度是O(n)或,其中是？O(n2)nlen(big_string)

我天真地想象我可以构建一个后缀trie,其中我保持每个节点的访问计数,然后计数大于1的最深节点是我正在寻找的结果集.

我有一个非常长的字符串(数百兆字节).我有大约1 GB的RAM.

这就是为什么用计数数据构建后缀trie在空间方面效率太低而无法为我工作.引用维基百科的后缀树:

存储字符串的后缀树通常比存储字符串本身需要更多的空间.

每个边缘和节点中的大量信息使得后缀树非常昂贵,在良好实现中消耗源文本的存储器大小的大约十到二十倍.后缀阵列将此要求降低到四倍,研究人员继续寻找更小的索引结构.

那是维基百科对树的评论,而不是特里.

如何在如此大量的数据中以及在合理的时间内(例如在现代台式机上不到一小时)找到长重复序列？

(一些维基百科链接,以避免人们将它们作为'答案'发布:字符串算法,特别是最长的重复子字符串问题 ;-))

这是从python中的字符串构建后缀数组的一种非常简单的方法:

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

但是,"content [a:]"会制作内容的副本,当内容变大时,内容会变得非常低效.所以我想知道是否有办法比较两个子串而不必复制它们.我试过使用buffer-builtin,但它没有用.

例如,给定字符串" abc fghi bc kl abcd lkm abcdefg ",该函数应返回字符串" abcd "并且计数为2.

AO(n ^ 2)解决方案似乎很容易,但我正在寻找更好的解决方案.

编辑:如果没有比O(n ^ 2)更好的方法,那么哪种方法最好的表现.

从手册页:

所述的strcmp()和STRNCMP()函数返回小于整数,等于或大于零,如果S1(或其前n个字节)被发现,分别为小于,以匹配或大于s2 .

实施例中的代码C(打印-15我的机器上,交换TEST1和TEST2反转值):

#include <stdio.h>
#include <string.h>

int main() {
    char* test1 = "hello";
    char* test2 = "world";
    printf("%d\n", strcmp(test1, test2));
}

我发现这个代码(取自这个问题)依赖于strcmp的值不是-1,0和1(它使用返回值qsort).对我来说,这是一种可怕的风格,取决于无证的功能.

我想我有两个相关的问题:

• C标准中是否有某些内容定义了返回值除了小于,大于或等于零之外的值？如果没有,标准实现有什么作用？
• 整个Linux,Windows和BSD的返回值是否一致？

编辑:

离开我的电脑5分钟后,我意识到问题代码实际上没有错误.在阅读评论/答案之前,我找出了我想出的部分,但是我把它留在那里以保持评论的相关性.我认为这仍然是一个有趣的问题,可能会导致习惯于其他语言的程序员总是返回-1,0或1(例如Python似乎这样做,但是没有记录这种方式).

FWIW,我认为依赖记录行为以外的其他东西是不好的风格.