【并查集】HAOI破译密文

【问题描述】
    信息的明文是由0利1组成的非空序列。但在网络通信中，为了信息的安全性，常对明文进行加密，用密文进行传输。密文是由0、1和若干个密码字母组成，每个密码字母代表不同的01串，例如，密文=011a0bf00a01。密码破译的关键是确定每个密码的含义。
    经过长期统计分析，现在知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文S1和S2，并且知道S1=S2，即两段密文代表相同的明文。你的任务是帮助情报人员对给定的两段密文进行分析，看一看有多少种可能的明文。
【输入文件】
第1行： S1 (第1段密文)
第2行： S2 (第2段密文)
第3行： N (密码总数， N<=26)
第4—N+3行： 字母i 长度i (密码用小写英文字母表示， 密码长度<=100)

【输出文件】
M（表示有M种可能的明文）

【输入输出样例】
encrypt.in
100ad1
cc1
4
a 2
d 3
c 4
b 50
encrypt.out
2
【约束条件】
明文的长度<=10000 　
注意：
如果两个密文出现矛盾情况，则输出0。
[size=x-large]【思路】树状并查集应用
将需要相等的位置的合并，
统计有ans组，
每种2个情况，
乘法原理

    [size=xx-large]var
    p:array ['a'..'z']of record b,e,l:longint; c:boolean; end;
    f,a1,a2:array [-2..10000] of longint;
    s1,s2:ansistring;c:char;
    n,i,l,j,x,y,ans,z,temp:longint;
    function father(x:longint):longint; begin
    if (f[x]=x)or(f[x]=0) then exit(f[x]) else
    begin
    f[x]:=father(f[x]);
    father:=f[x];
    end;
    end;
    procedure ex; begin
    write(0); close(input);close(output);halt;
    end;
    begin
    assign(input,'encrypt.in');reset(input);
    assign(output,'encrypt.out');rewrite(output);
    readln(s1);readln(s2);
    readln(n);
    for i:=1 to n do readln(c,p[c].l);
    for i:=1 to length(s1) do if (s1[i]<>'1')and(s1[i]<>'0') then p[s1[i]].c:=true;
    for i:=1 to length(s2) do if (s2[i]<>'1')and(s2[i]<>'0') then p[s2[i]].c:=true;
    l:=2;
    for c:='a' to 'z' do if p[c].c then 
         begin 
    	 p[c].b:=l;
    	 inc(l,p[c].l);
    	 p[c].e:=l-1;
    	 end;
    z:=l-1;
    for i:=1 to l do f[i]:=i;
    l:=0;
    for i:=1 to length(s1) do
         case s1[i] of
    	 '1':begin inc(l);a1[l]:=1;end;
    	 '0':begin inc(l);a1[l]:=0;end;
    	 else 
    	 begin
    	     for j:=p[s1[i]].b to p[s1[i]].e do
    		 begin
    		 inc(l);
    		 f[j]:=j;
    		 a1[l]:=j;
    		 end;
    	 end;end;
    l:=0;
    for i:=1 to length(s2) do
         case s2[i] of
    	 '1':begin inc(l);a2[l]:=1;if a1[l]=0 then ex; end;
    	 '0':begin inc(l);a2[l]:=0;if a1[l]=1 then ex; end;
    	 else 
    	 begin
    	     for j:=p[s2[i]].b to p[s2[i]].e do
    		 begin
    		 inc(l);
    		 f[j]:=j;
    		 a2[l]:=j;
    		 end;
    	 end;end;
    for i:=1 to l do
         begin
    	 x:=father(a1[i]);y:=father(a2[i]);
    	 if x+y=1 then ex;
    	 if x>y then f[x]:=y else f[y]:=x;
    	 end;
    ans:=0;f[1]:=1;
    for i:=2 to z do
    begin
    temp:=father(f[i]);
    if (temp<>1)and(temp<>0) then begin inc(ans);  f[temp]:=0;end;
    end;
    writeln(1 shl ans);
    close(input);close(output);
    end.