USACO analysis
杨菲凡 |
07 Dec 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
问题
在一个长度为 $N$ 的字符串中找出最短不重复的子字符串（连续）
思路
二分法找出最短长度
复杂度分析
二分法的复杂度为 $O(\log N)$，每次二分检查的复杂度为 $O(N)$，总复杂度为 $O(N \log N)$
代码
def valid(mid):
global n, letters
visited = set()
for i in range(n - mid + 1):
if letters[i:i + mid] not in visited:
visited.add(letters[i:i + mid])
else: return False
return True
lines = open('whereami.in').read().strip().split('\n')
n, letters = int(lines[0]), lines[1]
high = 100
low = 0
while high - low > 1:
mid = (high + low) // 2
if valid(mid): high = mid
else: low = mid
print(high)
file = open('whereami.out', 'w')
file.write(str(high))
file.close()
