我觉得这是弘扬自动机理论的优秀好题啊！
一些直觉是我们要对正反串建广义后缀自动机，然后接下来在此之上进行分析。
（本文将以 Border Jump 2 为例介绍 SAM 相关的一些性质）
翻转引理
对于任意字符串 S，必然有 S 的最大 3 操作次数等于 \text{rev}(S) 的最大 3 操作次数。
证：
考虑两者之间操作构成双射。
前缀引理
对于原串的任意子串 S 满足是所在 \text{endpos} 等价类内最长的字符串，其任意前缀 T 也一定是其所在 \text{endpos} 等价类内最长的字符串。
证：
反证，不妨设 \text{endpos}(a+T)=\text{endpos}(T)，不难发现此时易有 \text{endpos}(a+S)=endpos(S)。
好串引理 1
对于原串的任意子串 S，与最长的 S 子串 T 满足 \text{rev}(T) 为 S 后缀，\text{rev}(T) 必然是回文串或是其 \text{endpos} 等价类内最长字符串。
证：
反证，不妨设 T 不是回文串且不是其等价类内最长字符串。
取 T 在 S 中的任意出现位置，必然满足其与 S 后缀 \text{rev}(T) 不重叠（否则可以拼出长度严格不小于 |T| 的回文后缀）。
此时设 S=A+T+a+B+b+\text{rev}(T)，其中 A,B 均为可空字符串，a,b 为不等字符。
那么 \text{rev}(S)=T+b+\text{rev}(B)+a+\text{rev}(T)+\text{rev}(A)，由于 b+\text{rev}(T)\neq a+\text{rev}(T)，所以 \text{rev}(T) 是其所在 \text{endpos} 等价类内最长字符串。
好串引理 2
对于原串的任意子串 S ，与最长的 S 子串 T 满足 \text{rev}(T) 为 S 后缀，T 必然是回文串或满足 |T|\leq |\text{Parent}(S)|。
证：
如果 S=T 必然有 T 是回文串，于是用一遍好串引理 1 即可。
回文串引理
懒得写了总之是那堆可以用来求出回文串的最大 3 操作数的东西。
汇总
朴素做法是记 f_S 表示 S 的最大 3 操作数，以上若干个引理提示我们只需要处理出 S 是回文串或其所在等价类内最大字符串即可，根据回文树以及广义后缀自动机的理论告诉我们这两种的数量都是和原串长度线性相关的，具体维护把 \text{Parent} 树展开到 \text{dfn} 序上用可持久化线段树可以平凡地维护并做到 时间复杂度 O(|s|\log |s|)。