用滑动窗口应该能稍微快一点

000 ～ 999 所在位置索引一个表

没有限制的话，空间换时间，类似 ngram 索引

读取文件了，直接操作内存，分片多线程查找

字符串查找子串，kmp 算法

盲猜从圆周率里面取日期

我把文件下载下来了，用 str.find() 挺快的呀，读取文件 3.66s ，查找 0.007s

都是什么宰牛刀啊都，直接全量塞数据库啊！才多大点啊

PI 属于随机数那种，索引都不好建。

怕是没什么好办法。只能挨个查找。

@Vegetable 算法题哥哥

都是 O(n),
事先加载文件并事先分段并多线程

楼上说 kmp 的有没有看过 python 对于 find 的实现哇。。

@ppcoin 这是题吗，没看出来啊，这种问题最优解就是空间换时间，再怎么做不还是索引吗

有个数据结构叫后缀数组，特别适合你提出的这种文本不变，模式串不同的查询需求。

@hidemyself

请看 in 的实现

分片 线程查找

“这是题吗，没看出来啊，这种问题最优解就是空间换时间，再怎么做不还是索引吗”

问题的关键，是如何去建索引。完全乱序的数字，没办法建立有效的索引结构。

两秒出结果,很慢么?

预处理，用空间换时间是最优解法。只是六位到八位（而且盲猜是出生日期？那更简单了）的话存一张表轻松解决。

@hidemyself cpython 我印象里 str.find() 是用的 BMH 算法？反正虽然这个题面是个标准的 KMP 算法的场景，现实生产环境谁用谁是傻子。

最粗暴的就是 hash 呗，key 是数字，value 是位置，第一次构建比较慢，剩余的查询就都是 O(1)的了

不好意思，python 里叫字典，我习惯用 hash 指代 Java 里的 HashMap 了

trie 就行了吧，只是加载需要点时间，搞个常驻进程就行，我用 go 试了下内存大约 1G ，加载不到 10 分钟

这如果是个题，考的自然是子串匹配，Boyer-Moore 等。
就算建索引，也是用 trie 树系列，用 hash 有点太异想天开。。。

我也把文件下下来了，1.6 秒左右就找到了。如果是题目的话，这道题目是不合格的，因为现实情况就是用 find 就可以了，建索引还更慢

Ctrl + F

本地跑 str.find() 最多几秒种，速度足够了。

如果你有特别的需求，比如高并发服务，那就索引，数据库或者 hash 都行，不要读文本。

用数据库存上也是慢，内存里缓存起来性能最好了，下面代码大概意思是 converter 先统计好索引到数组，然后把数组写入到文件，finder 读入文件初始化数组，然后再查找。没仔细调试，因为太烧机器了，有兴趣的同学可以完善下：

1. converter.py
```python
# -*- coding:utf-8 -*-
#!/usr/bin/python3

import datetime

class PIConverter:
def __init__(self, minNum=100000, maxNum=99999999):
self.minNum = minNum
self.maxNum = maxNum
self.positions = [0]*(self.maxNum+1-self.minNum)

def convert(self, srcFile, dstFile):
fsrc = open(srcFile,'r')
fsrc.read(2)
try:
lastStr = ""
readSize = 1024*8
currPos = 0
readed = 0

starttime = datetime.datetime.now()

offset = len(str(self.minNum)) - 1
while True:
s = fsrc.read(readSize)
s = lastStr + s # 这里可以再优化下
currPos -= len(lastStr)
for i in range(len(s)-8):
strLen = len(str(self.minNum))
while strLen <= len(str(self.maxNum)):
subs = s[i:i+strLen]
strLen += 1
num = int(subs)
index = num - self.minNum
if self.positions[index] == 0:
self.positions[index] = currPos + i

if len(s) == 0:
break

lastStr = s[len(s)-5:]
currPos += readSize
readed += readSize
if readed % (1024*1024*8) == 0:
print("total read: {}, time used: {}s".format(readed, (datetime.datetime.now() - starttime).seconds))

print("total read: {}, time used: {}s".format(readed, (datetime.datetime.now() - starttime).seconds))
print("done")

try:
fdst = open(dstFile,'rw+')
for index in range(self.positions):
fdst.write(str(index)+"\n")
finally:
fdst.close()
finally:
fsrc.close()

def find(self, n):
if n < self.minNum or n > 99999999:
return -1
return self.positions[n - self.minNum]

piConverter = PIConverter()

# 把已经统计出来的生成更小的文件
piConverter.convert("./pi-billion.txt", "./pi-position.txt")

# converter 初始化太慢了，所以最好还是先 piConverter.convert 把已经统计出来的生成更小的文件，finder.py 用该文件初始化和做查找
# print("141592:", piConverter.find(141592))
# print("415926:", piConverter.find(415926))
```

2. finder.py
```python
# -*- coding:utf-8 -*-
#!/usr/bin/python3

class PIFinder:
def __init__(self, fname, minNum=100000, maxNum=99999999):
self.minNum = minNum
self.maxNum = maxNum
self.positions = [0]*(self.maxNum+1-self.minNum)
f = open(fname,'r')
try:
i = 0
for line in f:
num = int(line)
self.positions[i] = num
finally:
f.close()

def find(self, n):
if n < self.minNum or n > 99999999:
return -1
return self.positions[n - self.minNum]

piFinder = PIFinder("./pi-position.txt")
print("141592:", piFinder.find(141592))
print("415926:", piFinder.find(415926))
```

#32 文件尾、打开写文件的好像都有问题，平时不写 py ，实在不熟悉，v 站发代码也确实难受，对齐好像都没了

我提一个用素数来 Hash 查找的方法，大致如下：

1. 将 0-9 映射为 前 10 个素数 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
2. 用一个定长为 6/8 的滑动窗口遍历这个 pi 的字符串，每次增长的时候，当前的 hash 先除以最后一位数字对应的素数再乘以新增数字对应的素数，可以得到最新的 hash 数值
3. 如果当前 hash 数值与要寻找的数字的 hash 相等，则停下来进一步比对字符串

当然 直接乘以 10 加上新来的数字再对 10^7 取 mode 以更新 hash 也行

950MB 塞内存里也没多大啊。