前言
首先抛出一个问题: 给定300w字符串A, 之后给定80w字符串B, 需要求出 B中的每一个字符串, 是否是A中某一个字符串的子串. 也就是拿到80w个bool值....Suffix Array 介绍
在计算机科学里, 后缀数组(英语:suffix array)是一个通过对字符串的所有后缀经过排序后得到的数组。...让我们来认识几个概念:
子串 字符串S的子串r[i..j],i中从i到j-1这一段,就是顺次排列r[i],r[i+1],…,r[j-1]形成的子串。...我们的目的是, 找ear是否是A中四个字符串中的某一个的子串. 求出一个TRUE/FALSE.
那么我们首先求出A中所有的字符串德所有子串.放到一个数组里....需要强调的是, 这个”题目”是我在工作中真实碰到的, 使用暴力解法尝试之后, 由于效率太低, 在大佬指点下使用了SA. 30s解决问题.