HBC232778[JSOI2009]瓶子和燃料,gcd与exgcd[模板]KMP字符串匹配题解

天涯离梦残月幽梦算法基础篇 2023-11-13 17:35:02 112 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

中出现了，其出现位置为。，你还需要求出对于其每个前缀

给出两个只含大写英文字母的字符串 s_1 s 1 和 s_2 s 2 ，若 s1 s1 的区间 [l,r] [l,r]子串与 s_2 s 2 完全相同，则称 s_2 s 2 在 s_1 s 1 中出现了，其出现位置为 l l。现在请你求出 s_2 s 2 在 s_1 s 1 中所有出现的位置。定义一个字符串 s s 的 border 为 s s 的一个非 s s本身的子串 t t，满足 t t 既是 s s 的前缀，又是 s s 的后缀。对于 s_2 s 2 ，你还需要求出对于其每个前缀 s' s ′ 的最长 border t' t ′ 的长度。