说在前面
免得me某一天愚蠢到了连这道题都不会做 于是还是记录下来
题目
BZOJ4566传送门
题面
给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两 个子串中有一个位置不同
输入输出格式
输入格式： 输入仅两行，每行包含一个字符串
输出格式： 输出一行一个整数，表示答案
解法
好像做法还挺多的… me想的是统计每一个子串的贡献，于是对这两个串建一个 广义后缀自动姬（别被吓到了…只是建在一起而已） 然后每个节点维护cnt1和cnt2，第一个串主链的cnt1为1，第二个串主链cnt2为1，逆拓扑序累加上去 那么，对于自动姬上的每个节点，贡献就是
(len−p.len)∗cnt1∗cnt2
(
l
e
n
−
p
.
l
e
n
)
∗
c
n
t
1
∗
c
n
t
2
，即当前节点长度 * 从1选的方案数 * 从2选的方案数
下面是自带大常数的代码
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
long long ans ;
char ss[
200005] ;
int len , tp , head[
800006] , id_c ;
struct Node{
int cnt[
2] , len , id ;
map<int,Node*> ch ;
Node *par ;
} *root , *las , w[
800005] , *tw = w ;
struct Path{
int pre , to ;
}p[
800005] ;
void newNode( Node *&nd ,
int len ){
nd = ++ tw ; nd->len = len ;
nd->id = ++id_c ;
}
void Insert(
int id ,
bool cate ){
Node *nd , *tmp = las ;
newNode( nd , las->len +
1 ) ;
nd->cnt[cate] =
1 ;
for( ; tmp && !tmp->ch.count( id ) ; tmp = tmp->par )
tmp->ch[id] = nd ;
if( !tmp ) nd->par = root ;
else{
Node *B = tmp->ch[id] ;
if( B->len == tmp->len +
1 ) nd->par = B ;
else{
Node *nB ; newNode( nB , tmp->len +
1 ) ;
nB->par = B->par ;
nd->par = B->par = nB ;
nB->ch = B->ch ;
while( tmp && tmp->ch[id] == B )
tmp->ch[id] = nB , tmp = tmp->par ;
}
} las = nd ;
}
void dfs(
int &u ){
Node *nd = w + u ;
for(
int i = head[u] , v ; i ; i = p[i].pre ){
v = p[i].to ;
dfs( v ) ;
nd->cnt[
0] += w[v].cnt[
0] ;
nd->cnt[
1] += w[v].cnt[
1] ;
}
if( u !=
1 )
ans +=
1LL * nd->cnt[
0] * nd->cnt[
1] * ( nd->len - nd->par->len ) ;
}
void solve(){
for(
int i =
2 ; i <= id_c ; i ++ ){
p[++tp] = ( Path ){ head[ w[i].par->id ] , i } ;
head[ w[i].par->id ] = tp ;
} dfs( id_c =
1 ) ;
printf(
"%lld" , ans ) ;
}
int main(){
newNode( root ,
0 ) ; root->par = NULL ;
las = root ;
scanf(
"%s" , ss ) ; len =
strlen( ss ) ;
for(
int i =
0 ; i < len ; i ++ )
Insert( ss[i] -
'a' ,
0 ) ;
las = root ;
scanf(
"%s" , ss ) ; len =
strlen( ss ) ;
for(
int i =
0 ; i < len ; i ++ )
Insert( ss[i] -
'a' ,
1 ) ;
solve() ;
}
