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\) 才能转移。
已完成