如何优化非常长的字符串的子串查找?


有一个实例: http://www.angio.net/pi/piquery
作用是在Pi的小数点后两亿位中查找某段数字开始出现的位置,
比如输入123456,他告诉我们123456出现在小数点后2458885位
一个很经典的字符串子串查找算法,一般用Boyer–Moore或者KMP毫无压力,难点应该在于数据量比较大,原来的父串特别长。
它已经实现了,就比较好奇它背后的原理,两亿位数字差不多800M,虽然放内存也可以,但是否可以运用数据库来辅助存储?现在pi已经算到了两万亿都不止了(10^13),能够运用数据库意味着数据库的集群化也可以使用了。。(当然也没有人会无聊到用这么大的集群放个这么小的功能吧)

数据库 算法

超级帥蜀黍 10 years, 11 months ago

人家对如何做的有说明的好不, http://www.angio.net/pi/how.html

鲶鱼爱雨天 answered 10 years, 11 months ago

Your Answer