【ABC135F】Strings of Eternity

点击查看目录

目录

• • 题目概括
  • 判断无穷解
  • 对于有限解
  • 代码
• 我喜欢你

鲜花：老骥伏枥，志在伏枥。

推歌：【GUMI】恋空予報【電ポルP】

题面自己看。

atcoder题目链接

题目概括

嘻嘻。

判断无穷解

以下记字符串 \(t\) 重复 \(i\) 为 \(t^i\)，\(s^j\) 同理。

首先考虑无穷解的问题。

对于任何什么东西，如果他有一个循环周期为 \(p\)，另一个循环周期为 \(s\)，那么它存在循环周期是 \(gcd(s,p)\)，不难证明。

考虑到两个字符串 \(s^{\infty}\) 和 \(t^{\infty}\)，如果两个字符串匹配长度非常长，超过了两个串的循环周期 \(\lvert s \rvert\) 和 \(\lvert t \rvert\) 之和，那么两个串一定是由同一个更小的大小为 \(gcd(\lvert s\rvert,\lvert t\rvert)\) 循环节产生的。

但是 \(s\) 和 \(t\) 串存在“错位”是正常的，而如果能够匹配无限长的区间，错位的长度最长是 \(\lvert s\rvert+\lvert t\rvert-gcd(\lvert s\rvert,\lvert t\rvert)\)。

一旦匹配的长度超过 \(\lvert s\rvert+\lvert t\rvert-gcd(\lvert s\rvert,\lvert t\rvert)\)，后面的部分会因为周期的力量自动对齐，永远匹配下去。

将 \(t\) 的长度延申至 \(\lvert s\rvert+\lvert t\rvert-gcd(\lvert s\rvert,\lvert t\rvert)\)，\(s\) 比 \(t\) 大一个循环节，通过 kmp 匹配，\(t\) 能被全部匹配，那就是无限匹配的。

对于有限解

有限解，在刚刚 \(s\) 和 \(t\) 的延申中，已经断掉了，\(t\) 在 \(s\) 里断开了，不是子串。

所以无意义，kmp 匹配长度除以 \(\lvert t\rvert\) 即可。

代码

Miku's Code

我喜欢你

https://atcoder.jp/contests/abc135/submissions/71365895