题意

两个字符串是同构的,当且仅当可以通过一个单射关系的映射变成两个相等的字符串。给定一个字符串,询问不同构的子串个数。

分析

发现只有三种字符,那么单射关系只有 \(6\) 种。

一个字符串同构的字符串数量分为下面两种情况:

  • 如果这个字符串仅由一个字符构成,它有三种不同的同构字符串
  • 其他情况都有六种不同的同构字符串

于是,如果我们把仅由一个字符构成的字符串补成两倍,这道题目就变成了求不同的子串个数。

求不同的子串个数,我们根据六种映射关系,插入广义 sam 。直接算就好了。

仅有一个字符构成的字符串,显然就是原字符串中连续的最长长度的字符串。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注