[ABC141E] Who Says a Pun?
阅读原文时间:2023年08月22日阅读:1

2023-02-17

题目传送门

翻译

难度&重要性(1~10):4

题目来源

AtCoder

dp,字符串

看到求两个完全相同的子串时,我们可以发现其与求最长公共子串相似,只不过是在同一个字符串中求。因此我们可以使用求最长公共子串类似的 dp 转移。设 \(f_{i,j}\) 为以第 \(i\) 个字符结尾的子串与以第 \(j\) 个字符结尾的子串的公共子串长度,当 \(s_i=s_j\) 时,\(f_{i,j}=f_{i-1,j-1} + 1\)。

但还需要注意,两个子串互不重叠,因此需要满足 \(f_{i-1,j-1} \leq j - i-1\) 才能转移。

已完成

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器