其它综合

练习后缀数组

我爱IT资讯库   2021/02/19

一.字符串公共子串

1.poj2774long long message

要求尽量相同,那么将各个子串连在一起用lsquo;#rsquo;连接,查最长height,判一下sa位置就好了

代码:

 1 #includelt;cstdiogt;
 2 #includelt;cstringgt;
 3 #includelt;algorithmgt;
 4 using std::max;
 5 using std::min;
 6 using std::swap;
 7 const int n=1000000;
 8 int tmr[n];
 9 int rnk[n];
10 int has[n];
11 int hgt[n];
12 int sa[n];
13 int ln[n];
14 char str[n];
15 int n,cnt;
16 int len;
17 int ans;
18 bool same(int a,int b,int l)
19 {
20     if(a+lgt;len||b+lgt;len)
21         return false;
22     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
23 }
24 int main()
25 {
26     scanf("%s",str+1);
27     int len1=strlen(str+1);
28     for(len=1;lenlt;=len1;len++)
29         ln[len]=str[len];
30     scanf("%s",str+1);
31     ln[++len]=‘#‘;
32     int len2=strlen(str+1);
33     for(int i=1;ilt;=len2;i++)
34         ln[++len]=str[i];
35     for(int i=1;ilt;=len;i++)
36         has[ln[i]]++;
37     for(int i=0;ilt;128;i++)
38         if(has[i])
39             tmr[i]=++cnt;
40     for(int i=1;ilt;128;i++)
41         has[i]+=has[i-1];
42     for(int i=1;ilt;=len;i++)
43     {
44         sa[has[ln[i]]--]=i;
45         rnk[i]=tmr[ln[i]];
46     }
47     for(int k=1;cnt!=len;klt;lt;=1)
48     {
49         cnt=0;
50         for(int i=0;ilt;=len;i++)
51             has[i]=0;
52         for(int i=1;ilt;=len;i++)
53             has[rnk[i]]++;
54         for(int i=1;ilt;=len;i++)
55             has[i]+=has[i-1];
56         for(int i=len;i;i--)
57             if(sa[i]gt;k)
58                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
59         for(int i=1;ilt;=k;i++)
60             tmr[len-i+1]=has[rnk[len-i+1]]--;
61         for(int i=1;ilt;=len;i++)
62             sa[tmr[i]]=i;
63         for(int i=1;ilt;=len;i++)
64             if(same(sa[i],sa[i-1],k))
65                 tmr[sa[i]]=cnt;
66             else
67                 tmr[sa[i]]=++cnt;
68         for(int i=1;ilt;=len;i++)    
69             rnk[i]=tmr[i];
70     }
71     hgt[1]=0;
72     for(int i=1;ilt;=len;i++)
73     {
74         if(rnk[i]==1)    
75             continue;
76         int j=max(1,hgt[rnk[i-1]]-1);
77         while(ln[i+j-1]==ln[sa[rnk[i]-1]+j-1])
78             hgt[rnk[i]]=j++;
79     }
80     for(int i=2;ilt;=len;i++)
81     {
82         if(hgt[i]gt;ans)
83         {
84             int a=sa[i];
85             int b=sa[i-1];
86             if(agt;b)
87                 swap(a,b);
88             if(alt;=len1amp;amp;bgt;len1+1)
89                 ans=hgt[i];
90         }
91     }
92     printf("%d\n",ans);
93     return 0;
94 }

2.可重复可不对齐公共子串个数。

同理,在两个字符串中间加一个lsquo;#rsquo;连在一起。

查询hgt,显然,小于hgt的值都能取到,那么就单调栈优化一下。

理论上是双单调栈,但做两次也是一样的。

poj3415

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 typedef long long lnt;
  5 const int n=200005;
  6 int tmr[n];
  7 int rnk[n];
  8 int has[n];
  9 int hgt[n];
 10 int sa[n];
 11 int str[n];
 12 lnt s[n];
 13 lnt n[n];
 14 char tmp[n];
 15 int len;
 16 int cnt;
 17 int tt;
 18 int tp;
 19 bool same(int a,int b,int l)
 20 {
 21     if(a+lgt;len||b+lgt;len)
 22         return false;
 23     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 24 }
 25 void gsa(void)
 26 {
 27     memset(sa,0,sizeof(sa));
 28     memset(has,0,sizeof(has));
 29     memset(hgt,0,sizeof(hgt));
 30     memset(tmr,0,sizeof(tmr));
 31     cnt=0;
 32     for(int i=1;ilt;=len;i++)
 33         has[str[i]]++;
 34     for(int i=0;ilt;128;i++)
 35         if(has[i])
 36             tmr[i]=++cnt;
 37     for(int i=1;ilt;128;i++)
 38         has[i]+=has[i-1];
 39     for(int i=1;ilt;=len;i++)
 40     {
 41         sa[has[str[i]]--]=i;
 42         rnk[i]=tmr[str[i]];
 43     }
 44     for(int k=1;cnt!=len;klt;lt;=1)
 45     {
 46         cnt=0;
 47         for(int i=0;ilt;=len;i++)
 48             has[i]=0;
 49         for(int i=1;ilt;=len;i++)
 50             has[rnk[i]]++;
 51         for(int i=1;ilt;=len;i++)
 52             has[i]+=has[i-1];
 53         for(int i=len;i;i--)
 54             if(sa[i]gt;k)
 55                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 56         for(int i=1;ilt;=k;i++)
 57             tmr[len-i+1]=has[rnk[len-i+1]]--;
 58         for(int i=1;ilt;=len;i++)
 59             sa[tmr[i]]=i;
 60         for(int i=1;ilt;=len;i++)
 61             if(same(sa[i],sa[i-1],k))
 62                 tmr[sa[i]]=cnt;
 63             else
 64                 tmr[sa[i]]=++cnt;
 65         for(int i=1;ilt;=len;i++)
 66             rnk[i]=tmr[i];
 67     }
 68     return ;
 69 }
 70 void ght(void)
 71 {
 72     for(int i=1;ilt;=len;i++)
 73     {
 74         if(rnk[i]==1)
 75             continue;
 76         int j=std::max(1,hgt[rnk[i-1]]-1);
 77         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])
 78             hgt[rnk[i]]=j++;
 79     }
 80     return ;
 81 }
 82 int main()
 83 {
 84     while(1)
 85     {
 86         tp=0;
 87         memset(str,0,sizeof(str));
 88         len=0;
 89         scanf("%d",amp;tt);
 90         if(!tt)
 91             return 0;
 92         scanf("%s",tmp+1);
 93         int len1=strlen(tmp+1);
 94         for(int i=1;ilt;=len1;i++)
 95             str[++len]=tmp[i];
 96         str[++len]=‘#‘;
 97         scanf("%s",tmp+1);
 98         int len2=strlen(tmp+1);
 99         for(int i=1;ilt;=len2;i++)
100             str[++len]=tmp[i];
101         gsa();
102         ght();
103         lnt ans=0;
104         lnt sum=0;
105         tp=0;
106         for(int i=2;ilt;=len;i++)
107         {
108             if(hgt[i]lt;tt)
109             {
110                 sum=tp=0;
111                 continue;
112             }
113             lnt c=0;
114             while(tpamp;amp;hgt[i]lt;s[tp])
115             {
116                 sum-=(lnt)(s[tp]-tt+1)*n[tp];
117                 sum+=(lnt)(hgt[i]-tt+1)*n[tp];
118                 c+=n[tp];
119                 tp--;
120             }
121             tp++;
122             s[tp]=hgt[i];
123             n[tp]=c;
124             if(sa[i-1]lt;=len1)
125             {
126                 sum+=(lnt)(s[tp]-tt+1);
127                 n[tp]++;
128             }
129             if(sa[i]gt;len1+1)
130                 ans+=sum;
131         }
132         sum=0;
133         tp=0;
134         for(int i=2;ilt;=len;i++)
135         {
136             if(hgt[i]lt;tt)
137             {
138                 sum=tp=0;
139                 continue;
140             }
141             lnt c=0;
142             while(tpamp;amp;hgt[i]lt;s[tp])
143             {
144                 sum-=(lnt)(s[tp]-tt+1)*n[tp];
145                 sum+=(lnt)(hgt[i]-tt+1)*n[tp];
146                 c+=n[tp];
147                 tp--;
148             }
149             tp++;
150             s[tp]=hgt[i];
151             n[tp]=c;
152             if(sa[i-1]gt;len1+1)
153             {
154                 sum+=(lnt)(s[tp]-tt+1);
155                 n[tp]++;
156             }
157             if(sa[i]lt;=len1)
158                 ans+=sum;
159         }
160         printf("%lld\n",ans);
161     }
162     return 0;
163 }

二.二分check height数组

1.找最长重复子串

pojmusical theme

同一串中最长字串(要求不重叠)

二分答案,字典序相近后缀的前缀更趋向于相同。

查询时注意开始位置使其不重叠。

我不会告诉你我数组没清零wa了n次

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 using std::max;
  5 using std::min;
  6 int thm[500000];
  7 int rnk[500000];
  8 int has[500000];
  9 int tmr[500000];
 10 int hgt[500000];
 11 int sa[500000];
 12 int n;
 13 int cnt;
 14 bool same(int a,int b,int l)
 15 {
 16     if(a+lgt;n||b+lgt;n)
 17         return false;
 18     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 19 }
 20 bool check(int l)
 21 {
 22     int mx=-0x3f3f3f3f;
 23     int mn=0x3f3f3f3f;
 24     for(int i=2;ilt;=n;i++)
 25     {
 26         if(hgt[i]gt;=l)
 27         {
 28             mx=max(mx,max(sa[i],sa[i-1]));
 29             mn=min(mn,min(sa[i],sa[i-1]));
 30             if(mx-mngt;l)
 31                 return true;
 32         }else{
 33             mx=-0x3f3f3f3f;
 34             mn=0x3f3f3f3f;
 35         }
 36     }
 37     return false;
 38 }
 39 int main()
 40 {
 41     while(scanf("%d",amp;n)!=eof)
 42     {
 43         if(!n)
 44             return 0;
 45         memset(thm,0,sizeof(thm));
 46         memset(rnk,0,sizeof(rnk));
 47         memset(has,0,sizeof(has));
 48         memset(tmr,0,sizeof(tmr));
 49         memset(hgt,0,sizeof(hgt));
 50         memset(sa,0,sizeof(sa));
 51         for(int i=1;ilt;=n;i++)
 52         {
 53             scanf("%d",amp;thm[i]);
 54             has[i]=0;
 55         }
 56         n--;
 57         cnt=0;
 58         for(int i=1;ilt;=n;i++)
 59             thm[i]=thm[i+1]-thm[i]+88;
 60         thm[n+1]=0;
 61         for(int i=1;ilt;=n;i++)
 62             has[thm[i]]++;
 63         for(int i=0;ilt;=200;i++)
 64             if(has[i])
 65                 tmr[i]=++cnt;
 66         for(int i=1;ilt;=200;i++)
 67             has[i]+=has[i-1];
 68         for(int i=1;ilt;=n;i++)
 69         {
 70             sa[has[thm[i]]--]=i;
 71             rnk[i]=tmr[thm[i]];
 72         }
 73         for(int k=1;cnt!=n;klt;lt;=1)
 74         {
 75             cnt=0;
 76             for(int i=1;ilt;=n;i++)
 77                 has[i]=0;
 78             for(int i=1;ilt;=n;i++)
 79                 has[rnk[i]]++;
 80             for(int i=1;ilt;=n;i++)
 81                 has[i]+=has[i-1];
 82             for(int i=n;i;i--)
 83                 if(sa[i]gt;k)
 84                     tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 85             for(int i=1;ilt;=k;i++)
 86                 tmr[n-i+1]=has[rnk[n-i+1]]--;
 87             for(int i=1;ilt;=n;i++)
 88                 sa[tmr[i]]=i;
 89             for(int i=1;ilt;=n;i++)
 90                 if(same(sa[i],sa[i-1],k))
 91                     tmr[sa[i]]=cnt;
 92                 else
 93                     tmr[sa[i]]=++cnt;
 94             for(int i=1;ilt;=n;i++)
 95                 rnk[i]=tmr[i];
 96         }
 97         hgt[1]=0;
 98         for(int i=1;ilt;=n;i++)
 99         {
100             if(rnk[i]==1)
101                 continue;
102             int j=max(1,hgt[rnk[i-1]]-1);
103             while(thm[j+i-1]==thm[sa[rnk[i]-1]+j-1])
104                 hgt[rnk[i]]=j++;
105         }
106         int ans=0;
107         int l=0,r=n;
108         while(llt;=r)
109         {
110             int mid=(l+r)gt;gt;1;
111             if(check(mid))
112             {
113                 ans=mid;
114                 l=mid+1;
115             }else
116                 r=mid-1;
117         }
118         if(ansgt;=4)
119             printf("%d\n",ans+1);
120         else
121             puts("0");
122     }
123     return 0;
124 }

2.找重复次数大于k的子串,可重叠

poj 3261milk patterns

二分答案,找连续height大于k的即可。

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 using std::max;
  5 using std::min;
  6 const int n=2000000;
  7 int tmr[n];
  8 int rnk[n];
  9 int has[n];
 10 int hgt[n];
 11 int qlt[n];
 12 int sa[n];
 13 int n,k;
 14 int cnt;
 15 int ans;
 16 bool same(int a,int b,int l)
 17 {
 18     if(a+lgt;n||b+lgt;n)
 19         return false;
 20     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 21 }
 22 bool check(int l)
 23 {
 24     cnt=1;
 25     for(int i=2;ilt;=n;i++)
 26     {
 27         if(hgt[i]gt;=l)
 28         {
 29             cnt++;
 30             if(cntgt;=k)
 31                 return true;
 32         }else
 33             cnt=1;
 34     }
 35     return false;
 36 }
 37 int main()
 38 {
 39     scanf("%d%d",amp;n,amp;k);
 40     for(int i=1;ilt;=n;i++)
 41         scanf("%d",amp;qlt[i]);
 42     for(int i=1;ilt;=n;i++)
 43         has[qlt[i]]++;
 44     for(int i=0;ilt;=1000000;i++)
 45         if(has[i])
 46             tmr[i]=++cnt;
 47     for(int i=1;ilt;=1000000;i++)
 48         has[i]+=has[i-1];
 49     for(int i=1;ilt;=n;i++)
 50     {
 51         sa[has[qlt[i]]--]=i;
 52         rnk[i]=tmr[qlt[i]];
 53     }
 54     for(int k=1;cnt!=n;klt;lt;=1)
 55     {
 56         cnt=0;
 57         for(int i=0;ilt;=n;i++)
 58             has[i]=0;
 59         for(int i=1;ilt;=n;i++)
 60             has[rnk[i]]++;
 61         for(int i=1;ilt;=n;i++)
 62             has[i]+=has[i-1];
 63         for(int i=n;i;i--)
 64             if(sa[i]gt;k)
 65                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 66         for(int i=1;ilt;=k;i++)
 67             tmr[n-i+1]=has[rnk[n-i+1]]--;
 68         for(int i=1;ilt;=n;i++)
 69             sa[tmr[i]]=i;
 70         for(int i=1;ilt;=n;i++)
 71             if(same(sa[i],sa[i-1],k))
 72                 tmr[sa[i]]=cnt;
 73             else
 74                 tmr[sa[i]]=++cnt;
 75         for(int i=1;ilt;=n;i++)
 76             rnk[i]=tmr[i];
 77     }
 78     hgt[1]=0;
 79     for(int i=1;ilt;=n;i++)
 80     {
 81         if(rnk[i]==1)
 82             continue;
 83         int j=max(1,hgt[rnk[i-1]]-1);
 84         while(qlt[i+j-1]==qlt[sa[rnk[i]-1]+j-1])
 85             hgt[rnk[i]]=j++;
 86     }
 87     int l=0,r=n;
 88     while(llt;=r)
 89     {
 90         int mid=(l+r)gt;gt;1;
 91         if(check(mid))
 92         {
 93             ans=mid;
 94             l=mid+1;
 95         }else
 96             r=mid-1;
 97     }
 98     printf("%d\n",ans);
 99     return 0;
100 }

3.找字符串中连续出现x次子串。

poj3294life forms

二分答案,查询hgt连续大于某个值。

注意要用不同未出现连字符连接否则会被进行比较。

一共26个字母,100个串,可利用字符比较紧(我是不是傻,为啥不用数字)

把字母压到前面,利用后面的字符就好了。

注意存储最好用第一个(因为我闲的233)

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 const int n=200000;
  5 int tmr[n];
  6 int rnk[n];
  7 int has[n];
  8 int hgt[n];
  9 int sa[n];
 10 int str[n];
 11 char tmp[n];
 12 int len;
 13 int l[10000];
 14 bool vis[200];
 15 int blg[n];
 16 int cnt;
 17 int n;
 18 int sum;
 19 int ret[n];
 20 bool same(int a,int b,int l)
 21 {
 22     if(a+lgt;len||b+lgt;len)
 23         return false;
 24     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 25 }
 26 void gsa(void)
 27 {
 28     memset(tmr,0,sizeof(tmr));
 29     memset(rnk,0,sizeof(rnk));
 30     memset(has,0,sizeof(has));
 31     memset(hgt,0,sizeof(hgt));
 32     cnt=0;
 33     for(int i=1;ilt;=len;i++)
 34         has[str[i]]++;
 35     for(int i=0;ilt;128;i++)
 36         if(has[i])
 37             tmr[i]=++cnt;
 38     for(int i=1;ilt;128;i++)
 39         has[i]+=has[i-1];
 40     for(int i=1;ilt;=len;i++)
 41     {
 42         sa[has[str[i]]--]=i;
 43         rnk[i]=tmr[str[i]];
 44     }
 45     for(int k=1;cnt!=len;klt;lt;=1)
 46     {
 47         cnt=0;
 48         for(int i=0;ilt;=len;i++)
 49             has[i]=0;
 50         for(int i=1;ilt;=len;i++)
 51             has[rnk[i]]++;
 52         for(int i=1;ilt;=len;i++)
 53             has[i]+=has[i-1];
 54         for(int i=len;i;i--)
 55             if(sa[i]gt;k)
 56                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 57         for(int i=1;ilt;=k;i++)
 58             tmr[len-i+1]=has[rnk[len-i+1]]--;
 59         for(int i=1;ilt;=len;i++)
 60             sa[tmr[i]]=i;
 61         for(int i=1;ilt;=len;i++)
 62             if(same(sa[i],sa[i-1],k))
 63                 tmr[sa[i]]=cnt;
 64             else
 65                 tmr[sa[i]]=++cnt;
 66         for(int i=1;ilt;=len;i++)
 67             rnk[i]=tmr[i];
 68     }
 69     return ;
 70 }
 71 void ght(void)
 72 {
 73     for(int i=1;ilt;=len;i++)
 74     {
 75         if(rnk[i]==1)
 76             continue;
 77         int j=std::max(1,hgt[rnk[i-1]]-1);
 78         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])
 79             hgt[rnk[i]]=j++;
 80     }
 81     return ;
 82 }
 83 bool can(int x)
 84 {
 85     int ans=0;
 86     int num=0;
 87     memset(vis,0,sizeof(vis));
 88     int bgn=1;
 89     for(int i=2;ilt;=len;i++)
 90     {
 91         if(hgt[i]gt;=x)
 92         {
 93             if(!vis[blg[sa[i-1]]]amp;amp;blg[sa[i-1]])
 94             {
 95                 ans++;
 96                 vis[blg[sa[i-1]]]=true;
 97             }
 98             if(!vis[blg[sa[i]]]amp;amp;blg[sa[i]])
 99             {
100                 ans++;
101                 vis[blg[sa[i]]]=true;
102             }
103         }else{
104             if(ansgt;n/2)
105                 ret[++num]=sa[bgn];
106             ans=0;
107             bgn=i;
108             memset(vis,0,sizeof(vis));
109         }
110     }
111     if(ansgt;n/2)
112         ret[++num]=sa[len];
113     if(num)
114     {
115         sum=num;
116         return true;
117     }
118     return false;
119 }
120 int main()
121 {
122     while(1)
123     {
124         len=0;
125         sum=0;
126         memset(str,0,sizeof(str));
127         scanf("%d",amp;n);
128         if(!n)
129             return 0;
130         for(int i=1;ilt;=n;i++)
131         {
132             scanf("%s",tmp+1);
133             l[i]=strlen(tmp+1);
134             for(int j=1;jlt;=l[i];j++)
135             {
136                 str[++len]=tmp[j]-‘a‘;
137                 blg[len]=i;
138             }
139             l[i]=len;
140             str[++len]=26+i;
141             blg[len]=0;
142         }
143         gsa();
144         ght();
145         int l=0;
146         int r=len;
147         int lth=0;
148         while(llt;=r)
149         {
150             int mid=(l+r)gt;gt;1;
151             if(can(mid))
152             {
153                 lth=mid;
154                 l=mid+1;
155             }else
156                 r=mid-1;
157         }
158         if(llt;=1)
159             puts("");
160         else{
161             for(int i=1;ilt;=sum;i++)
162             {
163                 for(int j=0;jlt;lth;j++)
164                     printf("%c",str[j+ret[i]]+‘a‘);
165                 puts("");
166             }
167         }
168         puts("");
169     }
170     return 0;
171 }

4.最长复现式公共子串。

spoj220

用不同符号连接在一起。

二分查找check max-mingt;长度即可。

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 const int n=200000;
  5 int tmr[n];
  6 int rnk[n];
  7 int has[n];
  8 int hgt[n];
  9 int sa[n];
 10 int mn[20];
 11 int mx[20];
 12 int str[n];
 13 bool vis[20];
 14 int blg[n];
 15 char tmp[n];
 16 int len;
 17 int cnt;
 18 int n;
 19 bool same(int a,int b,int l)
 20 {
 21     if(a+lgt;len||b+lgt;len)
 22         return false;
 23     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 24 }
 25 void gsa(void)
 26 {
 27     for(int i=1;ilt;=len;i++)
 28         has[str[i]]++;
 29     for(int i=0;ilt;=200;i++)
 30         if(has[i])
 31             tmr[i]=++cnt;
 32     for(int i=1;ilt;=200;i++)
 33         has[i]+=has[i-1];
 34     for(int i=1;ilt;=len;i++)
 35     {
 36         sa[has[str[i]]--]=i;
 37         rnk[i]=tmr[str[i]];
 38     }
 39     for(int k=1;cnt!=len;klt;lt;=1)
 40     {
 41         cnt=0;
 42         for(int i=0;ilt;=len;i++)
 43             has[i]=0;
 44         for(int i=1;ilt;=len;i++)
 45             has[rnk[i]]++;
 46         for(int i=1;ilt;=len;i++)
 47             has[i]+=has[i-1];
 48         for(int i=len;i;i--)
 49             if(sa[i]gt;k)
 50                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 51         for(int i=1;ilt;=k;i++)
 52             tmr[len-i+1]=has[rnk[len-i+1]]--;
 53         for(int i=1;ilt;=len;i++)
 54             sa[tmr[i]]=i;
 55         for(int i=1;ilt;=len;i++)
 56             if(same(sa[i],sa[i-1],k))
 57                 tmr[sa[i]]=cnt;
 58             else
 59                 tmr[sa[i]]=++cnt;
 60         for(int i=1;ilt;=len;i++)
 61             rnk[i]=tmr[i];
 62     }
 63     return ;
 64 }
 65 void ght(void)
 66 {
 67     for(int i=1;ilt;=len;i++)
 68     {
 69         if(rnk[i]==1)
 70             continue;
 71         int j=std::max(1,hgt[rnk[i-1]]-1);
 72         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])
 73             hgt[rnk[i]]=j++;
 74     }
 75     return ;
 76 }
 77 void res(void)
 78 {
 79     for(int i=1;ilt;=n;i++)
 80     {
 81         vis[i]=0;
 82         mx[i]=-0x3f3f3f3f;
 83         mn[i]=0x3f3f3f3f;
 84     }
 85     return ;
 86 }
 87 bool check(int x)
 88 {
 89     for(int i=1;ilt;=n;i++)
 90     {
 91         if(mx[i]-mn[i]lt;x)
 92             return false;
 93     }
 94     return true;
 95 }
 96 bool can(int x)
 97 {
 98     res();
 99     for(int i=2;ilt;=len;i++)
100     {
101         if(hgt[i]gt;=x)
102         {
103             mx[blg[sa[i]]]=std::max(sa[i],mx[blg[sa[i]]]);
104             mx[blg[sa[i-1]]]=std::max(sa[i-1],mx[blg[sa[i-1]]]);
105             mn[blg[sa[i]]]=std::min(sa[i],mn[blg[sa[i]]]);
106             mn[blg[sa[i-1]]]=std::min(sa[i-1],mn[blg[sa[i-1]]]);
107             if(check(x))
108                 return true;
109         }else{
110             res();
111         }
112     }
113     return check(x);
114 }
115 int main()
116 {
117     int t;
118     scanf("%d",amp;t);
119     while(t--)
120     {
121         memset(tmr,0,sizeof(tmr));
122         memset(has,0,sizeof(rnk));
123         memset(hgt,0,sizeof(hgt));
124         memset(str,0,sizeof(str));
125         memset(blg,0,sizeof(blg));
126         len=cnt=0;
127         scanf("%d",amp;n);
128         for(int i=1;ilt;=n;i++)
129         {
130             scanf("%s",tmp+1);
131             int lx=strlen(tmp+1);
132             for(int j=1;jlt;=lx;j++)
133             {
134                 len++;
135                 blg[len]=i;
136                 str[len]=tmp[j];
137             }
138             str[++len]=i+128;
139         }
140         gsa();
141         ght();
142         int l=0;
143         int r=len;
144         int ans=0;
145         while(llt;=r)
146         {
147             int mid=(l+r)gt;gt;1;
148             if(can(mid))
149             {
150                 l=mid+1;
151                 ans=mid;
152             }else
153                 r=mid-1;
154         }
155         printf("%d\n",ans);
156     }
157     return 0;
158 }

三.相同串个数

spoj705

不同串个数,这里是求相同串的个数再使用容斥。

因为开始地方不同可以判定相同串就是对height求和

容斥一下,一个串共有len*(len+1)/2

代码:

 1 #includelt;cstdiogt;
 2 #includelt;cstringgt;
 3 #includelt;algorithmgt;
 4 using std::min;
 5 using std::max;
 6 const int n=1005;
 7 int tmr[n];
 8 int rnk[n];
 9 int has[n];
10 int hgt[n];
11 int sa[n];
12 char str[n];
13 int t;
14 int len;
15 int cnt;
16 int sum;
17 bool same(int a,int b,int l)
18 {
19     if(a+lgt;len||b+lgt;len)
20         return false;
21     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
22 }
23 int main()
24 {
25     scanf("%d",amp;t);
26     while(t--)
27     {
28         cnt=0;
29         memset(tmr,0,sizeof(tmr));
30         memset(rnk,0,sizeof(rnk));
31         memset(has,0,sizeof(has));
32         memset(hgt,0,sizeof(hgt));
33         memset(sa,0,sizeof(sa));
34         len=0;
35         sum=0;
36         scanf("%s",str+1);
37         len=strlen(str+1);
38         for(int i=1;ilt;=len;i++)
39             has[str[i]]++;
40         for(int i=0;ilt;128;i++)
41             if(has[i])
42                 tmr[i]=++cnt;
43         for(int i=1;ilt;128;i++)
44             has[i]+=has[i-1];
45         for(int i=1;ilt;=len;i++)
46         {
47             sa[has[str[i]]--]=i;
48             rnk[i]=tmr[str[i]];
49         }
50         for(int k=1;cnt!=len;klt;lt;=1)
51         {
52             cnt=0;
53             for(int i=0;ilt;=len;i++)    
54                 has[i]=0;
55             for(int i=1;ilt;=len;i++)
56                 has[rnk[i]]++;
57             for(int i=1;ilt;=len;i++)
58                 has[i]+=has[i-1];
59             for(int i=len;i;i--)
60                 if(sa[i]gt;k)
61                     tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
62             for(int i=1;ilt;=k;i++)
63                 tmr[len-i+1]=has[rnk[len-i+1]]--;
64             for(int i=1;ilt;=len;i++)
65                 sa[tmr[i]]=i;
66             for(int i=1;ilt;=len;i++)
67                 if(same(sa[i],sa[i-1],k))
68                     tmr[sa[i]]=cnt;
69                 else
70                     tmr[sa[i]]=++cnt;
71             for(int i=1;ilt;=len;i++)
72                 rnk[i]=tmr[i];
73         }
74         for(int i=1;ilt;=len;i++)
75         {
76             if(rnk[i]==1)
77                 continue;
78             int j=max(1,hgt[rnk[i-1]]-1);
79             while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])
80                 hgt[rnk[i]]=j++;
81         }
82         for(int i=2;ilt;=len;i++)
83             sum+=hgt[i];
84         int ans=((len+1)*len/2)-sum;
85         printf("%d\n",ans);
86     }
87     return 0;
88 }

四、rmq预处理获得相同前缀

1.判断回文串:

用倍增法事件复杂度不如manacher

判断一个串正着念反着念,以一个为中心答案。

先预判奇偶性。

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 using std::max;
  5 using std::min;
  6 const int n=10000;
  7 int tmr[n];
  8 int rnk[n];
  9 int hgt[20][n];
 10 int has[n];
 11 int sa[n];
 12 int str[n];
 13 int lg[n];
 14 int ln;
 15 int cnt;
 16 int len;
 17 char st[n];
 18 bool same(int a,int b,int l)
 19 {
 20     if(a+lgt;len||b+lgt;len)
 21         return false;
 22     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 23 }
 24 void gsa(void)
 25 {
 26     cnt=0;
 27     for(int i=1;ilt;=len;i++)
 28         has[str[i]]++;
 29     for(int i=0;ilt;=128;i++)
 30         if(has[i])
 31             tmr[i]=++cnt;
 32     for(int i=1;ilt;=128;i++)
 33         has[i]+=has[i-1];
 34     for(int i=1;ilt;=len;i++)
 35     {
 36         sa[has[str[i]]--]=i;
 37         rnk[i]=tmr[str[i]];
 38     }
 39     for(int k=1;cnt!=len;klt;lt;=1)
 40     {
 41         cnt=0;
 42         for(int i=0;ilt;=len;i++)
 43             has[i]=0;
 44         for(int i=1;ilt;=len;i++)
 45             has[rnk[i]]++;
 46         for(int i=1;ilt;=len;i++)
 47             has[i]+=has[i-1];
 48         for(int i=len;i;i--)
 49             if(sa[i]gt;k)
 50                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 51         for(int i=1;ilt;=k;i++)
 52             tmr[len-i+1]=has[rnk[len-i+1]]--;
 53         for(int i=1;ilt;=len;i++)
 54             sa[tmr[i]]=i;
 55         for(int i=1;ilt;=len;i++)
 56             if(same(sa[i],sa[i-1],k))
 57                 tmr[sa[i]]=cnt;
 58             else
 59                 tmr[sa[i]]=++cnt;
 60         for(int i=1;ilt;=len;i++)
 61             rnk[i]=tmr[i];
 62     }
 63 }
 64 void hgt(void)
 65 {
 66     hgt[0][1]=0;
 67     for(int i=1;ilt;=len;i++)
 68     {
 69         if(rnk[i]==1)
 70             continue;
 71         int j=max(1,hgt[0][rnk[i-1]]-1);
 72         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1]amp;amp;jlt;=len)
 73             hgt[0][rnk[i]]=j++;
 74     }
 75     for(int i=1;ilt;=18;i++)
 76         for(int j=1;j+(1lt;lt;i)-1lt;=len;j++)
 77             hgt[i][j]=min(hgt[i-1][j],hgt[i-1][j+(1lt;lt;(i-1))]);
 78     return ;
 79 }
 80 int min(int a,int b)
 81 {
 82     int l=lg[b-a+1];
 83     return min(hgt[l][a],hgt[l][b-(1lt;lt;l)+1]);
 84 }
 85 int lcp(int x,int y)
 86 {
 87     if(xgt;len||ygt;len)
 88         return 0;
 89     int a=min(rnk[x],rnk[y]);
 90     int b=max(rnk[x],rnk[y]);
 91     return min(a+1,b);
 92 }
 93 int main()
 94 {
 95     for(int i=2;ilt;=9000;i++)
 96         lg[i]=lg[i/2]+1;
 97     while(scanf("%s",st+1)!=eof)
 98     {
 99         memset(has,0,sizeof(has));
100         memset(tmr,0,sizeof(tmr));
101         memset(sa,0,sizeof(sa));
102         memset(hgt,0,sizeof(hgt));
103         memset(str,0,sizeof(str));
104         len=0;
105         ln=strlen(st+1);
106         for(int i=1;ilt;=ln;i++)
107             str[++len]=st[i];
108         str[++len]=‘#‘;
109         for(int i=ln;i;i--)
110             str[++len]=st[i];
111         gsa();
112         hgt();
113         int sta=1;
114         int ans=1;
115         for(int i=1;ilt;=len;i++)
116         {
117             int tmp=lcp(i,len-i+1);
118             if(tmp*2-1gt;ans)
119             {
120                 ans=tmp*2-1;
121                 sta=i-tmp+1;
122             }
123             tmp=lcp(i,len-i+2);
124             if(tmp*2gt;ans)
125             {
126                 ans=tmp*2;
127                 sta=i-tmp;
128             }
129         }
130         for(int i=0;ilt;ans;i++)
131             printf("%c",st[i+sta]);
132         puts("");
133     }
134     return 0;
135 }

2.寻找最长连续子串

poj3693

求出rmq,枚举局部的连续长度。

枚举起始点,在起始点向前扩展,更新答案。

代码:

  1 #includelt;cstdiogt;
  2 #includelt;cstringgt;
  3 #includelt;algorithmgt;
  4 const int n=100000;
  5 int tmr[n];
  6 int has[n];
  7 int rnk[n];
  8 int hgt[20][n];
  9 int sa[n];
 10 int lg[n];
 11 char str[n];
 12 int len;
 13 int cnt;
 14 bool same(int a,int b,int l)
 15 {
 16     if(a+lgt;len||b+lgt;len)
 17         return false;
 18     return (rnk[a]==rnk[b])amp;amp;(rnk[a+l]==rnk[b+l]);
 19 }
 20 void gsa(void)
 21 {
 22     cnt=0;
 23     memset(has,0,sizeof(has));
 24     memset(tmr,0,sizeof(tmr));
 25     memset(hgt,0,sizeof(hgt));
 26     for(int i=1;ilt;=len;i++)
 27         has[str[i]]++;
 28     for(int i=0;ilt;128;i++)
 29         if(has[i])
 30             tmr[i]=++cnt;
 31     for(int i=1;ilt;128;i++)
 32         has[i]+=has[i-1];
 33     for(int i=1;ilt;=len;i++)
 34     {
 35         sa[has[str[i]]--]=i;
 36         rnk[i]=tmr[str[i]];
 37     }
 38     for(int k=1;cnt!=len;klt;lt;=1)
 39     {
 40         cnt=0;
 41         for(int i=0;ilt;len;i++)
 42             has[i]=0;
 43         for(int i=1;ilt;=len;i++)
 44             has[rnk[i]]++;
 45         for(int i=1;ilt;=len;i++)
 46             has[i]+=has[i-1];
 47         for(int i=len;i;i--)
 48             if(sa[i]gt;k)
 49                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
 50         for(int i=1;ilt;=k;i++)
 51             tmr[len-i+1]=has[rnk[len-i+1]]--;
 52         for(int i=1;ilt;=len;i++)
 53             sa[tmr[i]]=i;
 54         for(int i=1;ilt;=len;i++)
 55             if(same(sa[i],sa[i-1],k))
 56                 tmr[sa[i]]=cnt;
 57             else
 58                 tmr[sa[i]]=++cnt;
 59         for(int i=1;ilt;=len;i++)
 60             rnk[i]=tmr[i];
 61     }
 62 }
 63 void ght(int *h)
 64 {
 65     h[1]=0;
 66     for(int i=1;ilt;=len;i++)
 67     {
 68         if(rnk[i]==1)
 69             continue;
 70         int j=std::max(1,h[rnk[i-1]]-1);
 71         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])
 72             h[rnk[i]]=j++;
 73     }
 74     return ;
 75 }
 76 void grmq(void)
 77 {
 78     for(int i=1;ilt;=19;i++)
 79         for(int j=1;j+(1lt;lt;i)-1lt;=len;j++)
 80             hgt[i][j]=std::min(hgt[i-1][j],hgt[i-1][j+(1lt;lt;(i-1))]);
 81     return ;
 82 }
 83 void init(void)
 84 {
 85     gsa();
 86     ght(hgt[0]);
 87     grmq();
 88     return ;
 89 }
 90 int rmq(int x,int y)
 91 {
 92     if(xgt;y)
 93         std::swap(x,y);
 94     int l=lg[y-x+1];
 95     return std::min(hgt[l][x],hgt[l][y-(1lt;lt;l)+1]);
 96 }
 97 int lcp(int x,int y)
 98 {
 99     x=rnk[x];
100     y=rnk[y];
101     if(xgt;y)
102         std::swap(x,y);
103     return rmq(x+1,y);
104 }
105 int main()
106 {
107     int tttttttt=0;
108     for(int i=2;ilt;n;i++)
109         lg[i]=lg[i/2]+1;
110     while(1)
111     {
112         tttttttt++;
113         scanf("%s",str+1);
114         if(str[1]==‘#‘)
115             return 0;
116         len=strlen(str+1);
117         init();
118         int ans=1;
119         int lns=1;
120         int sta=sa[1];
121         for(int ln=1;lnlt;=len/2;ln++)
122         {
123             for(int s=0;(s+1)*lnlt;=len;s++)
124             {
125                 int tmp=lcp(s*ln+1,(s+1)*ln+1);
126                 int pre=1;
127                 int tpl=s*ln+1;
128                 while(prelt;lnamp;amp;s*ln-pre+1gt;0amp;amp;str[s*ln-pre+1]==str[(s+1)*ln-pre+1])
129                 {
130                     tmp++;
131                     if(tmp%ln==0||rnk[tpl]gt;rnk[s*ln-pre+1])
132                         tpl=s*ln-pre+1;
133                     pre++;
134                 }
135                 if(lnslt;(tmp/ln+1)||(lns==(tmp/ln+1)amp;amp;rnk[sta]gt;rnk[tpl]))
136                 {
137                     sta=tpl;
138                     lns=tmp/ln+1;
139                     ans=lns*ln;
140                 }
141             }
142         }
143         printf("case %d: ",tttttttt);
144         for(int i=sta;ilt;sta+ans;i++)
145             printf("%c",str[i]);
146         puts("");
147     }
148     
149     return 0;
150 }

练习 后缀数组

原文地址:https://www.cnblogs.com/blog-dr-j/p/9697218.html




热门内容

【转】lamp环境搭建

【转】lamp环境搭建

学习PHP脚本编程语言之前,必须先搭建并熟悉开发环境,开发环境有很多种,例如LAMP、WAMP、MAMP等。这... ...

servlet三种实现方式之二继承GenericServlet开发

servlet有三种实现方式: 1.实现servlet接口 2.继承GenericServlet 3.... ...

InfoQ刚发表一篇论文《半静态语言–原理和价值分析》

半静态语言 – 背景、原理和价值 (Semi-Static Language  - Background,M... ...

Zend_Db_Table 表关联

  介绍: 在RDBMS中,表之间有着各种关系,有一多对应,多多对应等等。 Zend框架提供了一... ...

MySQL执行引擎有哪些

MyISAM: 优势 – 查询速度快 – 数据和索引压缩问题 – 表级锁 – 数据丢失 InnoDB: 优... ...

Centos7下yum搭建lnmp环境(yum安装方式)

我们都知道linux下安装软件主要有三种方式: 1.源码编译安装,即下载软件源代码,利用gcc g++ make 等编译 ...

\(^_^)/ Java实现各种排序算法

各种排序算法及其java程序实现 . 各种排序算法:冒择路(入)兮(稀)快归堆,桶式排序,基数排序 ... ...

hibernate空格导致的错误!

数据库中已经有两条记录,这是为了测试数据用的。 下面是我对hibernate中查询进行的测试.... package ...

上课思想分析过程

1.功能较多必须有菜单选择项2.针对题目避免重复时先将已生成的算式保存,然后将下一条生成的式子进行判断是否已生成,如果生 ...

存储过程不能删除之ORA-04043

同事问有一个存储过程在PL/SQL Developer中可以看到,但删除的时候报对象不存在。   ... ...

系统属性Properties历遍

package com.msmiles.test; import java.util.Enumeration; ... ...

在 linux x86-64 模式下分析内存映射流程

前言 在上一篇中我们分析了 linux 在 x86-32 模式下的虚拟内存映射流程,本章主要继续分析 linux 在 ... ...

一个过滤器类,过滤多个路径

<!-- 登录验证 --> <filter> <filter-name>... ...

网页中的平衡、对比、连贯和留白

网页中的平衡、对比、连贯和留白 <!-- Body Copy --> 网页设计中需要把握好很多原则和细节,... ...
好高兴啊

好高兴啊

  好高兴啊…..好高兴啊….终于发现了…..   ... ...

WCF技术剖析(卷1)之目录

第1章  WCF简介 (WCF Overview)      ... ...

EXT核心API详解(五)

[转载]EXT核心API详解(五)-Ext.EventManager/EventObject/CompositeElem... ...

xorg如何使用 xkbprint?

问题:手册中没有例子,我所尝试的每个文件都需要一些几何。$ xkbcomp/usr/share/x11/xkb/symb ...
织梦淘宝客常见问题

织梦淘宝客常见问题

一、下载安装 见官方帖子,不细说。http://bbs.dedecms.com/203194.html 在此强烈建议新手... ...

(转)批处理(bat)全盘搜索指定文件获取其完整路径方法大全

本文总结了4种实现全盘搜索指定文件获取其完整路径的bat批处理文件源码,有需要的朋友可以参考下 【方案一】fo... ...

Java线程讲解

一 线程的基本概念 线程是一个程序内部的顺序控制流.一个进程相当于一个任务,一个线程相当于一个任务中的一条执行路径. ... ...

css display:none和visibility:hidden和visible="false"区别

  如果在p的style中把visibility设为 hidden则p隐藏,但是它会占据空白空间,... ...

ASP.NET[1]

   有很多人学过ASP,用ASP做过网站,可是到ASP .NET环境下发现,变化真是太大了... ...

构建一个安全的软件系统时,可能遇到的风险及解决方案(未完)

随着汽车工业的发展,汽车早以不是那个由一堆零件组成的大机器,而是由机械和电子器件构成的整体系统。并且,这个... ...
VPS上安装ShadowSocks

VPS上安装ShadowSocks

shadowsocks 是一个轻量级隧道代理,用来穿过防火墙。 我的VPS机器安装的是CentOS系统、... ...

ResultSet 调用getString 抛出NullPointException问题的解决

在Java连接数据库时,有时候在ResultSet 调用getString (或其他类似的方法),有时候会抛出Nu... ...

浅谈OSIV与泛型DAO模式

open session in view  简称 OSIV 模式 在Hibernate中能更好的应... ...

数据库设计原理:数据建模的三个阶段

如果你在Google或者百度上搜索数据建模,相信可以搜索出很多关于数据建模的文章,但是你会发现其中绝大部分是理论、... ...

ajaxfileupload.js 文件上传

一,前台代码。 <input id="fileToUpload" type="... ...

ios的标志常量

1 dec 2 fixed 3 hex 4 internal 5 left 6 oct 7 right 8 scien ...