这东西真是学一次忘一次，为了不再忘了它也为了之后讲课可能要讲这玩意，所以梳理一下基本子串结构的一些基本逻辑。这不是学习笔记，更类似于提纲，所以讲得比较抽象……QwQ假设我们不是苛求严谨性的理论计算机科学研究者，而只是一位期望用基本子串结构做做题的一名普通OIer。那么关于它

题面传送门卡常的出题人什么时候似啊？如果\(l=1,r=|t|\)，那么就是蠢得不能再蠢的问题：直接扔到AC自动机上跑匹配就好了，可以做到\(O(\sum|s|+|t|)\)。现在询问的变成了

考虑拆开贡献，前缀贡献痕容易算。而跨越\([l-1,l]\)的贡献，考虑在正串ACAM找到\([1,l-1]\)，反串ACAM找到\([l,r]\)，那么要做的就是在两串的fail链祖先上，找到能凑成完

先说一下自己的SAM做法：看到回文串我们首先考虑对以下字符串建立SAM：正串+特殊字符1+特殊字符2+反串。这样也许能有一点用。晚上睡觉前我考虑的是对于正串的endpos在反串中

建出反串的SAM，考虑其parenttree。发现一组满足条件的$A,B$，其对应的\(A\)和\(AB\)在树上必然有祖先关系，且根据原题定义满足如下条件：\(A\)的\(endpos\)集合不