BZOJ4566:[HAOI2016]找相同字符

Description

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两

个子串中有一个位置不同。

Input

两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母

Output

输出一个整数表示答案

Sample Input

aabb
bbaa

Sample Output

题解：

将两个字符串共同建出一个SAM（即先用A串建出SAM，再将last指为root，用B串继续建）。

这样，我们只用知道每个节点在A串中对应几个串、在B串中对应几个串（即在A、B中的size），在每次遍历到时相乘加到答案上。

求size的方法是将A、B串分别输入到自动机中，得到初始size1、size2，然后分别在pre树中dfs求出最终size1、size2。

访问节点i对答案的贡献为size1[i]*size2[i]，可以记忆化搜索统计答案，或利用某个性质（升级版：只有长度大于等于k的子串才被统计）。

代码：

 1 var
 2   i,j,k,l,n,m,now,last,t,cnt:longint;
 3   ans:int64;
 4   a:array[0..800005,'a'..'z']of longint;
 5   pre,step,c:array[0..800005]of longint;
 6   size1,size2:array[0..800005]of int64;
 7   b:array[0..800005,1..2]of longint;
 8   s1,s2:ansistring;
 9   ch:char;
10 function max(x,y:longint):longint;
11 begin if x>y then exit(x); exit(y); end;
12 procedure ss1(x,y:longint);
13 begin
14   inc(size1[x]);
15   if y>=length(s1)then exit;
16   ss1(a[x,s1[y+1]],y+1);
17 end;
18 procedure ss2(x,y:longint);
19 begin
20   inc(size2[x]);
21   if y>=length(s2)then exit;
22   ss2(a[x,s2[y+1]],y+1);
23 end;
24 procedure ss3(x:longint);
25 var i:longint;
26 begin
27   i:=c[x];
28   while i>0 do
29   begin
30     ss3(b[i,1]);
31     size1[x]:=size1[x]+size1[b[i,1]];
32     size2[x]:=size2[x]+size2[b[i,1]];
33     i:=b[i,2];
34   end;
35 end;
36 begin
37   readln(s1); readln(s2);
38   pre[0]:=-1; m:=0; last:=0;
39   for i:=1 to length(s1) do
40   begin
41     inc(m); now:=m; step[now]:=step[last]+1;
42     while(last<>-1)and(a[last,s1[i]]=0)do
43     begin a[last,s1[i]]:=now; last:=pre[last]; end;
44     if last=-1 then begin pre[now]:=0; last:=now; continue; end;
45     if step[last]+1=step[a[last,s1[i]]] then
46     begin pre[now]:=a[last,s1[i]]; last:=now; continue; end;
47     j:=a[last,s1[i]];
48     inc(m); a[m]:=a[j]; pre[m]:=pre[j]; step[m]:=step[last]+1;
49     pre[j]:=m; pre[now]:=m;
50     while last<>-1 do
51     begin
52       if a[last,s1[i]]=j then a[last,s1[i]]:=m else break;
53       last:=pre[last];
54     end;
55     last:=now;
56   end;
57   last:=0;
58   for i:=1 to length(s2) do
59   begin
60     inc(m); now:=m; step[now]:=step[last]+1;
61     while(last<>-1)and(a[last,s2[i]]=0)do
62     begin a[last,s2[i]]:=now; last:=pre[last]; end;
63     if last=-1 then begin pre[now]:=0; last:=now; continue; end;
64     if step[last]+1=step[a[last,s2[i]]] then
65     begin pre[now]:=a[last,s2[i]]; last:=now; continue; end;
66     j:=a[last,s2[i]];
67     inc(m); a[m]:=a[j]; pre[m]:=pre[j]; step[m]:=step[last]+1;
68     pre[j]:=m; pre[now]:=m;
69     while last<>-1 do
70     begin
71       if a[last,s2[i]]=j then a[last,s2[i]]:=m else break;
72       last:=pre[last];
73     end;
74     last:=now;
75   end;
76   cnt:=0;
77   for i:=1 to m do
78   begin inc(cnt); b[cnt,1]:=i; b[cnt,2]:=c[pre[i]]; c[pre[i]]:=cnt; end;
79   ss1(0,0); ss2(0,0); ss3(0); ans:=0;
80   for i:=1 to m do
81   ans:=ans+(size1[i]*size2[i])*(step[i]-max(k,step[pre[i]]+1)+1);
82   writeln(ans);
83 end.

View Code