HDU 5769 Substring

题目：Substring

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5769

题意：每个样例给出1个字符c 和1个字符串s ，问s的所有不同子串中包含字符c 的有多少。

思路：

　　好可惜当时比赛没看这题，不然就过了，算是一道比较简单的后缀数组题了。难点可能就在于后缀数组的掌握了，当时我学后缀数组的时候直感觉自己智商不够，说实话，要理解那十几行的代码确实有点难。

　　一个字符串s 的所有子串，可以理解成所有后缀的每一个前缀。比如abcd 的所有子串就是：abcd（a、ab、abc、abcd），bcd（b、bc、bcd），cd（c、cd），d（d）。这样子我们就可以用后缀数组解决问题了。

　　简单介绍下后缀数组的几个数组：

　　sa[i] 表示后缀排名为i 的下标。

　　height[i] 表示排名为i 和i-1 的后缀的最长公共前缀长度。

　　我们按排名从第一名开始遍历所有后缀，每一次再遍历这个后缀的每一个前缀，遇到s[j]=c 就退出来，那么这个后缀的所有前缀中，含有c 的有len-j个，比如现在处理的后缀是uvwxyz，c=x，那么遍历到x时，x=c，说明uvwx、uvwxy、uvwxyz三个子串含有c ，也就是len-j个，j是下标，下标从0开始。然后，下一个排名i 的后缀不需要从sa[i]开始遍历，假设height[i]=10，那么说明后缀i 的前10个前缀在之前已经遇到过，处理过了。如果在这10个没有c ，那么从sa[i]+height[i]开始遍历即可，如果这10个里包含了c ，因为题目要求不同子串，那么这个后缀的贡献就是len-sa[i]-height[i]。思路大概就这样，细节处理一下就可以过了。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 #define N 200020
 5 char s1[200020];
 6 int ws[N],wv[N];
 7 int sa[N],r[N],wx[N],wy[N];
 8 int height[N];
 9 bool cmp(int *r,int a,int b,int l)
10 {
11   return r[a]==r[b]&&r[a+l]==r[b+l];
12 }
13 void da(int *r,int n,int m)
14 {
15   //注意，这里的n必须比原始数组大小大1
16   int *x=wx,*y=wy;
17   for(int i=0;i<m;i++) ws[i]=0;
18   for(int i=0;i<n;i++) ws[x[i]=r[i]]++;
19   for(int i=1;i<m;i++) ws[i]+=ws[i-1];
20   for(int i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
21   //这里的x[i] 表示下标i的第一关键字排名
22   int i,j,p,*t;
23   for(j=1,p=1;p<n;j*=2,m=p)
24   {
25     for(p=0,i=n-j;i<n;i++) y[p++]=i;
26     for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
27     //此时的y[i] 表示第二关键字排第i的下标是y[i]
28     for(i=0;i<n;i++) wv[i]=x[y[i]];
29     for(i=0;i<m;i++) ws[i]=0;
30     for(i=0;i<n;i++) ws[wv[i]]++;
31     for(i=1;i<m;i++) ws[i]+=ws[i-1];
32     for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
33     for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
34       x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
35   }
36   for(int i=0;i<n;i++)
37   {
38     r[sa[i]]=i;
39   }
40 }
41 void calHeight(int n)
42 {
43   int h=0;
44   for(int i=0;i<n;i++)
45   {
46     if(r[i]==0) h=0;
47     else
48     {
49       int k=sa[r[i]-1];
50       if(--h<0) h=0;
51       while(s1[k+h]==s1[i+h]) h++;
52     }
53     height[r[i]]=h;
54   }
55 }
56 
57 int main()
58 {
59   int t,cas=1;
60   char s2[2];
61   scanf("%d",&t);
62   while(t--)
63   {
64     scanf("%s%s",s2,s1);
65     int len=strlen(s1);
66     for(int i=0;i<len;i++)
67       r[i]=s1[i]-'a'+1;
68     r[len]=0;
69     da(r,len+1,27);
70     calHeight(len+1);
71     long long sum=0;  //总和
72     int pre=100010;   //前一个遍历多少次才遇到c ，如果一直没遇到置为100010
73     char c=s2[0];
74     for(int i=1;i<=len;i++)
75     {
76       int j;
77       if(height[i]>pre)
78       {
79         sum+=len-sa[i]-height[i];
80         continue;
81       }
82       else j=sa[i]+height[i];
83       pre=height[i];
84       for(;s1[j];j++)
85       {
86         if(s1[j]!=c) pre++;
87         else break;
88       }
89       if(len-j==0) pre=100010;
90       sum+=len-j;
91     }
92     printf("Case #%d: %I64d
",cas++,sum);
93   }
94   return 0;
95 }