hk_cnyali's Blog

一个比较简单的图论问题，总算是填了这个小坑

给出一个长度为$n$的字符串$s_1$，由小写字母组成

定义一个字符串序列$s_{1 \sim k}$，满足性质：$s_i$在$s_{i-1} (i\ge2)$中出现至少两次（位置可重叠）

求最大的$k$是多少，使得从$s_1$开始到$s_k$都满足这样一个性质

$n\le 2\times 10^5$

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$表示它从第 $i$个字符开始的后缀，求：

$\sum_{1 \le i < j \le n} len(T_i)+len(T_j)-2*lcp(T_i,T_j)$

给出一个长度为的字符串和序列

对于$\forall r\in [0, n-1]$求$\sum_{i\ne j} [lcp(suf_i, suf_j)\ge r]$和$\max_{i\neq j,lcp(suf_i,suf_j)\ge r} a_i\times a_j$

给出$n$个由小写字母构成的字符串，求它们最长的公共子串的长度

$n\le 5, \sum|S|\le 10000$

给定一个长度为 $n$ 的字符串 $S$

$m$ 次询问，每次询问给出 $a,b,c,d$

求 $S[a,b]$的所有子串和子串$S[c,d]$的LCP（最长公共前缀）的最大值。

$n,m\le10^5$

19.3.31UPD

其实是一些很基础很入门很傻逼的东西，就不加密了

给定一个模板串$S$，多组询问，每次给出一个询问字符串$T$和一个区间$(l,r)$

求$T$有多少个本质不同的子串没有在$S$的$[l,r]$这段区间当中出现

$|S|, |T|\le 5*10^5, \sum|T|\le 10^6$