题目链接
题意
给你两个字符串 s t，求有多少种方案数将s选连续一部分放前面，t选连续一部分放后面组成回文串。 并且s选中的长度大于t选中长度 t必须选中包含第一个位置的区间
思路
枚举s串每个位置
i
i
i，答案为 每个位置
i
i
i 的最长以
i
i
i 为结尾的s串后缀匹配t串前缀 乘以 以
i
+
1
i+1
i+1为起点的回文串数量
分别使用二分hash和回文自动机求得。
代码
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
#define ull unsigned long long
const int N
= 1000005;
char s1
[N
], s2
[N
];
struct myHash
{
ull h
[N
], p
[N
];
const ull seed
= 19491001;
void init(char *s
) {
p
[0] = 1;
h
[0] = 0;
int len
= strlen(s
+1);
for(int i
= 1; i
<= len
; ++i
) {
p
[i
] = p
[i
-1]*seed
;
h
[i
] = h
[i
-1]*seed
+s
[i
];
}
}
ull
gethash(int l
, int r
) {
return h
[r
]-h
[l
-1]*p
[r
-l
+1];
}
}mh1
, mh2
;
const int M
= 26;
struct tree
{
int nxt
[N
][M
], fail
[N
], s
[N
], len
[N
];
int cnt
[N
];
int last
, n
, p
;
int num
[N
], id
[N
];
int newnode(int l
) {
for(int i
= 0; i
< M
; ++i
) nxt
[p
][i
] = 0;
len
[p
] = l
;
cnt
[p
] = 0;
num
[p
] = 0;
return p
++;
}
void init() {
p
= 0;
newnode(0);
newnode(-1);
last
= 0;
n
= 0;
s
[n
] = -1;
fail
[0] = 1;
}
int getfail(int x
) {
while(s
[n
-len
[x
]-1] != s
[n
]) x
= fail
[x
];
return x
;
}
void add(int c
) {
c
-= 'a';
s
[++n
] = c
;
int cur
= getfail(last
);
if(!nxt
[cur
][c
]) {
int now
= newnode(len
[cur
]+2);
fail
[now
] = nxt
[getfail(fail
[cur
])][c
];
nxt
[cur
][c
] = now
;
num
[now
] = num
[fail
[now
]]+1;
}
last
= nxt
[cur
][c
];
++cnt
[last
];
id
[n
] = last
;
}
void getcnt() {
for(int i
= p
-1; ~i
; --i
) cnt
[fail
[i
]] += cnt
[i
];
}
}my
;
int f(int mid
, int i
) {
if(mh1
.gethash(i
,i
+mid
-1) == mh2
.gethash(1,mid
)) return 1;
return 0;
}
int main() {
scanf("%s%s",s1
+1,s2
+1);
int n
= strlen(s1
+1), m
= strlen(s2
+1);
for(int i
= 1; i
<= n
/2; ++i
) swap(s1
[i
],s1
[n
-i
+1]);
ll ans
= 0;
my
.init();
for(int i
= 1; i
<= n
; ++i
) my
.add(s1
[i
]);
mh1
.init(s1
);
mh2
.init(s2
);
for(int i
= 1; i
<= n
; ++i
) {
int l
= 0, r
= min(i
,m
), la
, mid
;
while(l
<= r
) {
mid
= l
+r
>>1;
if(f(mid
,n
-i
+1)) la
= mid
, l
= mid
+1;
else r
= mid
-1;
}
ans
+= 1ll*la
*my
.num
[my
.id
[n
-i
]];
}
printf("%lld\n",ans
);
return 0;
}
