我们有一个语言X,它有一个字节和两个字节的字符.该语言具有以下特征.
问题是,我们得到一个任意长度的字符串和指向字符串中某个字节的指针,我们必须找出前一个字符是什么,下一个字符是什么.
一个简单的方法是从字符串的开头开始,检查字节的值并比较指针直到我们到达给定的指针.但在最坏的情况下,如果给定指针指向给定字符串中的最后一个字节,我们必须循环遍历所有字符.
我想知道是否有更好的算法可以在不考虑字符串长度的情况下以恒定时间给出结果？
bob*_*nce 12
不,恒定时间是不可能的,因为最坏的情况是,如Olexiy所述,几乎整个字符串都是顶部位设置的字节,你需要回溯到开始,找出哪个是第一个顶部位设置的字节在第一个双字节序列中.
希望这种病态很罕见,您可以一次退回一个字节,直到遇到任何低字节,在这种情况下,您可以确定它后面的字节是字符的开头.然后,您可以再次向前走,直到遇到原始指针.
在最坏的情况下,我们需要通过整个字符串.只考虑字符A = 100和B = 200,C = 201以及以下长度为N的字符串:
S1 = ABCBCBC ...... BC
S2 = BBCBCBC ...... BC