1032.字符流

1 · · March 25, 2023, 7:39 a.m.
var meting_api='https://meting.yany.ml/api?server=:server&type=:type&id=:id&r=:r'1032.字符流题目描述:设计算法,接收字符流,并检查这些字符的后缀是否是字符串数组 words中的一个字符串。数据范围: 1\le words \le 2000,1\le words[i]\le 200 最多调用查询 4\times 10^4 次。题解:解法一:trie 树将 words 中的字符串反转,然后插入trie中,每次接收一个字符之后,反向在 trie 树中查找该字符串前缀,如果存在返回 True,否则返回 False。解法二:AC自动机使用AC自动机建立字典图,因为AC自动机查找的时候不匹配会查找最长的后缀。建立字典图,然后从树根开始,每次接收一个字符就移动,如果存在该字符串,返回 True,否则就跳到 Fail 指针,一直跳。注意,可能需要使用指针来减少空间的使用。代码:解法一:1234567891011121314151617181920212223242526272829303132333435363738...