相关疑难解决方法(0)

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

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

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

摘自编程珍珠第15.2节

可在此处查看C代码:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

当我使用suffix-array在Python中实现它时:

example = open("iliad10.txt").read()
def comlen(p, q):
    i = 0
    for x in zip(p, q):
        if x[0] == x[1]:
            i += 1
        else:
            break
    return i

suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:]))  #VERY VERY SLOW

max_len = -1
for i in range(example_len - 1):
    this_len = comlen(example[idx[i]:], example[idx[i+1]:])
    print this_len
    if this_len > max_len:
        max_len = this_len
        maxi = i

我发现这idx.sort一步很慢.我认为它很慢,因为Python需要通过值而不是指针传递子串(如上面的C代码).

测试文件可以从这里 …

我编写了不同的 python 代码来反转给定的字符串。但是，无法弄清楚其中哪一个是有效的。有人可以使用时间和空间复杂度指出这些算法之间的差异吗？

def reverse_1(s):
      result = ""
      for i in s : 
          result = i + result
      return result

def reverse_2(s): 
      return s[::-1]

有已经有一些解决方案在那里，但我无法找出时间和空间复杂度。我想知道需要多少空间s[::-1]？

由于 python 会逐个复制，因此切片字符串的成本可能非常高。

我有一个对字符串进行操作的递归算法。具体来说，如果一个函数被传递了一个 string a，该函数会在a[1:]传递的 string上调用自己。问题在于字符串太长，逐个复制机制正在成为删除第一个字符的非常昂贵的方法。

有没有办法解决这个问题，还是我需要完全重写算法？

在 C++ 中，如果我要从字符串中删除第一个字符，它将类似于：

string s = "myreallylongstring";
s = s.substr(1);

这将是 O(1)。[如果我错了请纠正我]

然而，在 Python 的“不可变字符串”世界中，这段代码的运行时间复杂度是 O(n) 吗？

s = "myreallylongstring"
s = s[1:]

如果我使用字符列表会更快吗？

给定一个字符串s长度为n，切片操作s[i : j]在Python 3中，其中
(0 <=i <= j <= n)，需要多少时间在大O符号？

是 O(n) 或 O(1) 还是其他什么？

编辑

在python 3中切片列表和字符串是否有任何实现差异？