模板来源：http://blog.csdn.net/zkfzkfzkfzkfzkfzkfzk/article/details/9669747
解法参考：http://blog.csdn.net/dyx404514/article/details/9631787
刚学后缀自动机，还是有很多性质不是很了解……目前也就能做个模板题orz
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm> using namespace std; #define N 2010
#define MAXQ 10010 struct Suffix_Automaton
{
int F[N << ],ant,last,ch[N << ][],step[N << ]; void init()
{
last = ant = ;
memset(F,,sizeof(F));
memset(ch,,sizeof(ch));
memset(step,,sizeof(step));
} void ins(int x)
{
int t = ++ant, pa = last;
step[t] = step[last] + ;
last = t;
for( ; pa && !ch[pa][x]; pa = F[pa] )
ch[pa][x] = t;
if( pa == ) F[t] = ;
else if( step[pa] + == step[ ch[pa][x] ] )
F[t] = ch[pa][x];
else
{
int nq = ++ant, q = ch[pa][x];
memcpy( ch[nq], ch[q], sizeof(ch[nq]) );
step[nq] = step[pa] + ;
F[nq] = F[q];
F[q] = F[t] = nq;
for( ; pa && ch[pa][x] == q; pa = F[pa] )
ch[pa][x] = nq;
}
}
};
//以上为后缀自动机模板 struct node
{
int l, r;
int id;
}; node qry[MAXQ];
char str[];
int ans[MAXQ];
Suffix_Automaton SAM; bool cmp( node a, node b )
{
if ( a.l == b.l ) return a.r < b.r;
return a.l < b.l;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%s", &str[] );
int Q;
scanf( "%d", &Q );
for ( int i = ; i < Q; ++i )
{
scanf("%d%d", &qry[i].l, &qry[i].r );
qry[i].id = i;
}
sort( qry, qry + Q, cmp ); int preL = qry[].l;
SAM.init();
int j = preL;
for ( int i = ; i < Q; ++i )
{
if ( qry[i].l == preL )
{
while ( j <= qry[i].r )
{
SAM.ins( str[j] - 'a' );
++j;
}
int tmp = ;
for ( int k = SAM.ant; k > ; --k )
tmp += SAM.step[k] - SAM.step[ SAM.F[k] ];
ans[ qry[i].id ] = tmp;
}
else
{
preL = qry[i].l;
j = qry[i].l;
SAM.init();
while ( j <= qry[i].r )
{
SAM.ins( str[j] - 'a' );
++j;
}
int tmp = ;
for ( int k = SAM.ant; k > ; --k )
tmp += SAM.step[k] - SAM.step[ SAM.F[k] ];
ans[ qry[i].id ] = tmp;
}
} for ( int i = ; i < Q; ++i )
printf( "%d\n", ans[i] );
}
return ;
}
推荐几篇学习后缀自动机的文章：
陈立杰课件：http://wenku.baidu.com/view/7afa5828ed630b1c59eeb512.html
推荐资料：
http://fanhq666.blog.163.com/blog/static/8194342620123352232937/