给定一个字符串 s 快速响应查询 (i, j, k, l)与:
-
-1如果s[i..j] < s[k..l] -
0如果s[i..j] = s[k..l] -
1如果s[i..j] > s[k..l]
假设
-
i <= j -
k <= l -
0 <= i, k < s.length - 1
换句话说，执行大量的字典顺序子串比较。
s[i..j]是 (j - i + 1) -character 子字符串从位置 i 开始(从 0 开始索引)并在位置 j 结束(含)。
s[i..j] < s[i..j+1] ，即单词的前缀被认为小于单词本身)。
因为查询的数量，也就是O(s.length) ，应该快速回答查询，即对数时间或常数时间。我听说有传言说恒定时间解决方案是可能的(显然需要一些预处理)。
到目前为止，我考虑过使用哈希函数，例如
h[i] = (h[i - 1] + x^i * s[i]) mod m
哪里x > 26 (字母表的大小)和 m是素数。
s[i..j] 的哈希值然后将通过减去 h[i] 来计算来自 h[j]并除以 x到一个(尚未确定的)权力。
这种方法有一个严重的问题 - 它不允许我检查小于/大于条件。我最初认为 h[i..j] < h[k..l]应该暗示s[i..j] < s[k..l] .这是无效的，因为
- 取模。
- 让我们考虑字符串
azzz和b，让我们假设m足够大，所以我们不必执行模运算。很明显h['azzz'] > h['b']但是azzz < b.
这是作业。我不是在寻找实现，而是我应该了解更多的一般想法和问题。一个完整的解决方案当然是受欢迎的，但不是必需的。
最佳答案
我猜你来自波兰，所以这是一篇很棒的文章，对这个问题有很好的解决方法: http://www.mimuw.edu.pl/~jrad/wpg/drobne_oszustwo.pdf
事实上，您可以使用散列法检查哪个词更大。您必须使用 bin search 来查找这两个子字符串的第一个后缀，它具有不同的哈希值，然后检查下一个字母。它将指示更大的词。复杂度为 O(logm)，其中 m 是较短子字符串的大小。可以在O(1)中找到hash(使用幂的预处理)，然后进行bin search，也就是O(logm)。希望对您有所帮助:)
关于algorithm - 子串比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34957773/