题意
给一个长度为n的字符串，m次询问(l,r)求l到r内本质不同的回文子串数量
题解
看各路题解，一脸懵逼
终于在《金策 字符串算法选讲》中找到了关键疑惑答案
先说暴力
离线询问对r排序，考虑增加一个字符，右边界到了r，每次在回文树上暴力跳fail统计以r为结尾的新增回文串。注意到每一个回文串影响的左端点是一个区间
比如说当前枚举到的回文串为b，那么左区间落在 [上次b出现的位置的起点+1,本次b的起点]时，数量要增加1，那么用树状数组区间加就可以了，复杂度 O(n2logn)
考虑优化
引理1
一个字符串的所有回文后缀的长度,可以形成 k个等差数列, k是 log级的
意思是说，一个回文串的所有回文后缀，可以划分成不超过log个序列，每个序列都是一个等差数列（按照串的长度）
定义
前缀 pre(s, x) = s[1…x], 后缀 suf(s, x) = s[n − x + 1…n]
若 0 ≤ r < |s|, pre(s, r) = suf(s, r), 就称 pre(s, r) 是 s 的border
引理2
s 是回文串, 则 s 的后缀 t 是回文串当且仅当 t 是 s 的border
意思是说
t 是 s 的回文后缀，那么 s 的前缀 t′(长度等于 t )，也是回文串，并且，和 t 相同！
进一步说， t 的上一次出现的位置为 t′。
考虑更新
右端点右移一位时，考虑新增加的回文串，根据引理1，可以分为不超过log个等差数列，我们整个数列一起处理
见下图，最长的1的上一次出现的位置不知道，需要在线段树中找到
根据引理2，串2的上次出现的位置为串1的等长的前缀，所以棕色部分+1, 串3的上次出现位置为串2 的等长前缀，所以浅蓝色的部分+1，综合，我们要更新的位置就是 [串1的上次出现的开始位置+1,串3的开始位置] ,
问题只剩下在线段树中找了
首先，要建立fail树，dfs序
fail数有一个性质，结点的子树，表示的回文串的右端点都是一致的
从上面可知，对于每一个序列，我们只用找最长的回文串
用线段树维护回文串出现位置的最大值
每次，我们在串1 的对应fail树中的节点找他的子树的最大值，根据fail树的性质，子树中一定都出现了串1，并且右端位置相同
然后，用树状数组进行区间操作
代码
#include<bits/stdc++.h>
#define N 300010
#define INF 0x3f3f3f3f
#define eps 1e-6
#define pi 3.141592653589793
#define mod 1000000007
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;
char s[N];
LL ans=0;
vector<pp> Q[N];
struct SegTree
{
int a[N<<2];
int query(int x,int l,int r,int fl,int fr){
if (l==fl && r==fr) return a[x];
int t=(l+r)>>1;
if (fr<=t)return query(x<<1,l,t,fl,fr);else
if (fl>t) return query(x<<1|1,t+1,r,fl,fr);else
return max(query(x<<1,l,t,fl,t),query(x<<1|1,t+1,r,t+1,fr));
}
void updata(int x,int l,int r,int pos,int y){
if (l==r){ a[x]=y;return;}
int t=(l+r)>>1;
if (pos<=t) updata(x<<1,l,t,pos,y);else
updata(x<<1|1,t+1,r,pos,y);
a[x]=max(a[x<<1],a[x<<1|1]);
}
}Seg;
struct BIT{
int d[N];
void updata(int x,int y){for(int i=x;i<N;i+=i&-i)d[i]+=y;}
int sum(int x){int res=0;for(int i=x;i;i-=i&-i)res+=d[i];return res;}
}BT;
struct PAM {
int next[N][26] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
int fail[N] ;//fail指针，失配后跳转到fail指针指向的节点
int len[N] ;//len[i]表示节点i表示的回文串的长度
int s[N] ;//存放添加的字符
int id[N];
int last ;//指向上一个字符所在的节点，方便下一次add
int n ;//字符数组指针
int p ;//节点指针
int in[N],out[N],d[N],up[N],dfn=0;
vector<int>G[N]; //dfs序
//r为结尾的回文串的长度一定可以分成logn段等差数列
inline int newnode ( int l ) {//新建节点
for ( int i = 0 ; i < 26 ; ++ i ) next[p][i] = 0 ;
len[p] = l ;
return p ++ ;
}
inline void init () {//初始化
p =0 ;
newnode ( 0 ) ; newnode ( -1 ) ;
last = 0 ;
n = 0 ;
s[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
fail[0] = 1 ;
}
inline int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
while ( s[n - len[x] - 1] != s[n] ) x = fail[x] ;
return x ;
}
inline void add ( int c,int cc ) {
c -= 'a' ;
s[++ n] = c ;
int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
int now = newnode ( len[cur] + 2 ) ;//新建节点
fail[now] = next[get_fail ( fail[cur] )][c] ;
next[cur][c] = now ;
d[now]=len[now]-len[fail[now]];
up[now]=(d[fail[now]]==d[now]?up[fail[now]]:now);
}
last = next[cur][c] ;
id[cc]=last;
}
void build(){ //建立fail树
for(int i=0;i<p;i++)if(i!=1) G[fail[i]].pb(i);
}
void dfs(int x=1){ //dfs序
in[x]=++dfn;
for(auto i:G[x]) dfs(i);
out[x]=dfn;
}
void slove(){
for(int i=1;i<=n;i++){
for(int j=id[i];j;j=fail[up[j]]){//遍历所有i为结尾的回文串，按照等差整块遍历，最多log次
int l=max(1,Seg.query(1,1,dfn,in[j],out[j])-len[j]+2);
int r=i-len[up[j]]+2;
BT.updata(l,1); BT.updata(r,-1);
}
Seg.updata(1,1,dfn,in[id[i]],i);
for(auto j:Q[i])
ans=(ans+1ll*j.se*BT.sum(j.fi))%mod;
}
}
}A;
int main(int argc, char const *argv[])
{
int n,m; scc(n,m); scanf("%s",s+1);
A.init();
for(int i=1;i<=n;i++) A.add(s[i],i);
A.build();A.dfs();
for(int i=1;i<=m;i++){
int l,r; scc(l,r); Q[r].pb(pp(l,i));
}
A.slove();
printf("%lld\n",ans);
return 0;
}
京公网安备 11010502036488号