A12*_*321 3 algorithm
我有两个循环缓冲区 - 如何判断一个是另一个循环？
例如B1 = 1,1,2,1,8,1,5,7,B2 = 2,1,8,1,5,7,1,1我们可以说B1和B2是相等的,因为我可以旋转其中一个来获得另一个.
B1 = 1,1,2,1,8,1,5,7
B2 = 2,1,8,1,5,7,1,1
测试这种平等的最佳算法是什么？明显的测试是O(n^2)(只是比较缓冲区 - n逐步 - 从它们的每个n元素开始),但我相信我已经看到了线性时间算法.你能指点我吗？
O(n^2)
n
zch*_*zch 6
假设B1并且B2具有相同的长度,您的问题等同于询问"是B2一个子串B1 + B1"(B1与自身连接).
B1
B2
B1 + B1
例如:4元素字符串是1234if且仅当它是子字符串时的旋转12341234.
1234
12341234
检查一个字符串是否是另一个字符串的子字符串可以使用KMP算法在线性时间内完成.
归档时间：
11 年，2 月 前
查看次数：
171 次
最近记录：
9 年，1 月 前