tem*_*def 7 string algorithm big-o
一个pangrammatic窗口是一个包含字母的所有26个字母一块较大的文本的字符串.引用维基百科的一个例子,给出了这个文本:
我唱歌,以为我唱得很好; 但他只是带着一种非常古怪的表情抬头看着我的脸,然后说,"你唱歌多久了,小姐？"
文本中最小的pangrammatic窗口是这个字符串:
非常好; 但他只是带着一个非常古怪的前任抬头看着我的脸
其中每个字母至少包含一次.
我的问题是:给定一个文本语料库,找到文本中最小的pangrammatic窗口的最有效算法是什么？
我已经给出了一些想法,并已经提出了以下算法.我有一种强烈的感觉,这些并不是最佳的,但我认为我会将它们作为起点发布.
有一个简单的天真算法,它在时间O(n 2)和空间O(1)中运行:对于字符串中的每个位置,从该位置向前扫描并跟踪您看到的字母(可能在一个位向量中, ,因为只有26个不同的字母,占用空间O(1)).一旦你找到了所有26个字母,就会得到从该给定点开始的最短的pangrammatic窗口的长度.每次扫描可能需要时间O(n),并且有O(n)次扫描,总共为O(n 2)次.
我们还可以使用修改的二进制搜索在时间O(n log n)和空间O(n)中解决该问题.构造26个数组,每个字母对应一个字母,然后按照排序顺序使用输入文本中每个字母的位置填充这些数组.我们可以通过简单地扫描文本,将每个索引附加到与当前字符对应的数组来实现.一旦我们有了这个,我们可以在时间O(log n)中找到从某个索引开始的最短pangrammatic窗口的长度,在数组中运行26个二进制搜索,以找到每个字符在输入数组中出现的最早时间或者在给定的指数之后.无论这些数字中的哪一个最大,都会给出在字符串中最下方的"长极"字符,从而给出pangrammatic窗口的端点.运行此搜索步骤需要O(log n)时间,并且由于我们必须对字符串中的所有n个字符执行此操作,因此总运行时间为O(n log n),其中数组的内存使用量为O(n).
上述方法的进一步改进是用van Emde Boas树和前任搜索替换数组和二进制搜索.这将创建时间增加到O(n log log n),但是对于具有O(n)空间使用的O(n log log n)的净运行时,每个搜索时间减少到O(log log n)时间.
那里有更好的算法吗？
对于每一封信都要记录最近的观察情况.每当您处理一个字母时,更新相应的目击指数并计算所有字母上的目击指数的范围(最大 - 最小).找到最小范围的位置.
复杂度O(n).O(nlog(m))如果你考虑字母大小m.
该算法具有O(M)空间复杂度和O(N)时间复杂度(时间不依赖于字母大小M):
如果不是字符计数器,则存储字符串中的位置,可以稍微改进该算法.在这种情况下,步骤2应该只读取这些位置并与当前位置进行比较,步骤1应该更新这些位置并且(大部分时间)搜索文本中的某些字符.