专栏首页mlhdu 3518 (后缀数组)

hdu 3518 (后缀数组)

  题目描述:   找出一个字符串中至少重复出现两次的字串的个数(重复出现时不能重叠)。

  code:

     后缀数组处理,对于得到height 进行查找...  参考http://blog.csdn.net/mishifangxiangdefeng/article/details/7109211博主的详细的代码思路

  1     #include<iostream>
  2     #include<string>
  3     using namespace std;
  4     #define N 1200
  5     string s;
  6     int n, sa[4*N], rank[N], height[N];
  7     int buf[4*N], ct[N], sx[N], sax[N];
  8     inline bool leq(int a, int b, int x, int y)
  9     {
 10         return (a < x || a == x && b <= y);
 11     }
 12     inline bool leq(int a, int b, int c, int x, int y, int z)
 13     {
 14         return (a < x || a == x && leq(b, c, y, z));
 15     }
 16     inline int geti(int t, int nx, int sa[])
 17     {
 18         return (sa[t]<nx ? sa[t]*3+1 : (sa[t]-nx)*3+2);
 19     }
 20         //基数排序
 21     static void radix(int a[], int b[], int s[], int n, int k)
 22     { // sort a[0..n-1] to b[0..n-1] with keys in 0..k from s
 23         int i, t, sum;
 24         memset(ct, 0, (k + 1) * sizeof(int));
 25         for (i = 0; i < n; ++i) ct[s[a[i]]]++;
 26         for (i = 0, sum = 0; i <= k; ++i)
 27         {
 28             t = ct[i]; ct[i] = sum; sum += t;
 29         }
 30         for (i = 0; i < n; i++) b[ct[s[a[i]]]++] = a[i];
 31     }
 32 
 33     /*
 34     倍增算法,构造后缀数组的最坏时间复杂度为O(nlogn)。
 35     参数:
 36     int *r:待排序的字符串放在 r 数组中 , 从 r[0] 到 r[n-1] , 长度为 n , 且最大值小于 m 。
 37     为了函数操作的方便,约定除r[n-1] 外所有的 r[i] 都大于 0, r[n-1]=0 。
 38     int *sa:函数结束后,结果放在 sa 数组中,从 sa[0] 到 sa[n-1] 。 
 39     */
 40     void suffix(int s[], int sa[], int n, int k)
 41     { // !!! require s[n] = s[n+1] = s[n+2] = 0, n >= 2.
 42         int i, j, e, p, t;
 43         int name = 0, cx = -1, cy = -1, cz = -1;
 44         int nx = (n+2)/3, ny = (n+1)/3, nz = n/3, nxz = nx+nz;
 45         int *syz = s + n + 3, *sayz = sa + n + 3;
 46         for (i=0, j=0; i < n + (nx - ny); i++)
 47         if (i%3 != 0) syz[j++] = i;
 48         radix(syz , sayz, s+2, nxz, k);
 49         radix(sayz, syz , s+1, nxz, k);
 50         radix(syz , sayz, s , nxz, k);
 51         for (i = 0; i < nxz; i++)
 52         {
 53             if (s[ sayz[i] ] != cx || s[ sayz[i] + 1 ] != cy ||s[ sayz[i] + 2 ] != cz)
 54             {
 55                 name++; cx = s[ sayz[i] ];
 56                 cy = s[ sayz[i] + 1 ]; cz = s[ sayz[i] + 2 ];
 57             }
 58             if (sayz[i] % 3 == 1) syz[ sayz[i] / 3 ] = name;
 59             else syz[ sayz[i]/3 + nx ] = name;
 60         }
 61         if (name < nxz)
 62         {
 63             suffix(syz, sayz, nxz, name);
 64             for (i = 0; i < nxz; i++) syz[sayz[i]] = i + 1;
 65         }
 66         else
 67         {
 68             for (i = 0; i < nxz; i++) sayz[syz[i] - 1] = i;
 69         }
 70         for (i = j = 0; i < nxz; i++)
 71         if (sayz[i] < nx) sx[j++] = 3 * sayz[i];
 72         radix(sx, sax, s, nx, k);
 73         for (p=0, t=nx-ny, e=0; e < n; e++)
 74         {
 75             i = geti(t, nx, sayz); j = sax[p];
 76             if ( sayz[t] < nx ?leq(s[i], syz[sayz[t]+nx], s[j], syz[j/3]) :
 77                 leq(s[i], s[i+1], syz[sayz[t]-nx+1],
 78             s[j], s[j+1], syz[j/3+nx]) )
 79             {
 80                 sa[e] = i;
 81                 if (++t == nxz)
 82                 {
 83                     for (e++; p < nx; p++, e++)
 84                     sa[e] = sax[p];
 85                 }
 86             }
 87             else
 88             {
 89                 sa[e] = j;
 90                 if (++p == nx) for (++e; t < nxz; ++t, ++e)
 91                 sa[e] = geti(t, nx, sayz);
 92             }
 93         }
 94     }
 95 
 96     /*
 97     后缀数组 SA 是一个一维数组,它保存 1..n 的某个排列SA[1],SA[2],……,SA[n],
 98     并且保证 Suffix(SA[i]) < Suffix(SA[i+1]) , 1 ≤ i<n 。
 99     也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入 SA 中。 
100     */
101     void makesa()
102     {
103         memset(buf, 0, 4 * n * sizeof(int));
104         memset(sa, 0, 4 * n * sizeof(int));
105         for (int i=0; i<n; ++i) buf[i] = s[i] & 0xff;
106         suffix(buf, sa, n, 255);
107     }
108 
109 
110 
111     /*
112     名次数组 Rank[i] 保存的是 Suffix(i) 在所有后缀中从小到大 排列的 “ 名次 ” 。
113     容易看出,后缀数组和名次数组为互逆运算。
114     设字符串的长度为 n 。
115     为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小。
116     在求出名次数组后,可以仅用 O(1) 的时间比较任意两个后缀的大小。
117     在求出后缀数组或名次数组中的其中一个以后,便可以用 O(n) 的时间求出另外一个。
118     任意两个后缀如果直接比较大小,最多需要比较字符 n 次,也就是说最迟在比较第 n 个字符时一定能分出 “ 胜负 ” 。 
119     */
120     void getRank()
121     {
122         for(int i = 1;i < n; ++ i)
123             rank[sa[i]] = i;
124     }
125     /*
126     对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv},也就是从头开始顺次比较u和v的对应字符,对应字符持续相等的最大位置,
127     称为这两个字符串的最长公共前缀。
128     对正整数i,j定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])),其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个
129     和第j个后缀的最长公共前缀的长度。
130     定义一维数组height,令height[i]=LCP(i-1,i),1<i≤n,并设height[1]=0。
131     */
132     void lcp()
133     { // O(4 * N)
134         int i, j, k;
135         for (j = rank[height[i=k=0]=0]; i < n - 1; i++, k++)
136             while (k >= 0 && s[i] != s[ sa[j-1] + k ])
137                 height[j] = (k--), j = rank[ sa[j] + 1 ];
138     }
139     int main()
140     {
141 
142         while(cin>>s && s[0] != '#')
143         {
144             n = s.length() + 1;
145             makesa();
146             getRank();
147             lcp();
148             int ans = 0, minid, maxid;
149             //枚举字串长度h
150             for(int i = 1; i <= (n >> 1); i++)
151             {
152                 minid = 1200, maxid = -1;
153                 //对于每一次的h,利用height数组,找出连续的height大于等于h的里面最左端和最右端得为之l和r。
154                 for(int j = 2; j < n; j++)
155                     if (height[j] >= i)
156                     {
157                         if (sa[j - 1] < minid) minid = sa[j - 1];
158                         if (sa[j - 1] > maxid) maxid = sa[j - 1];
159                         if (sa[j] < minid) minid = sa[j];
160                         if (sa[j] > maxid) maxid = sa[j];
161                     }
162                     else
163                     {
164                         //如果l + h - 1 < r的话,说明没有重叠,答案加1.
165                         if (maxid != -1 && minid + i <= maxid) ans++;
166                         minid = 1200, maxid = -1;
167                     }
168                 //如果l + h - 1 < r的话,说明没有重叠,答案加1.
169                 if (maxid != -1 && minid + i <= maxid) ans++;
170             }
171            cout<<ans<<endl;
172         }
173         return 0;
174     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hdu---(1054)Strategic Game(最小覆盖边)

    Strategic Game Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/3...

    Gxjun
  • HDUOJ --2544最短路(基础)

    输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛...

    Gxjun
  • nyoj 115------城市平乱( dijkstra // bellman )

    城市平乱 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 南将军统领着N个部队,这N个部队分别驻扎在N个不同的城市。 他在用这N个...

    Gxjun
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • 河南理工大学新生挑战赛

    B.The flower 题意:意思就是给一个字符串,然后从字符串中得到子串,并且子串满足情况 1.出现次数大于2,; 2.子串的长度等于k; 找到有多...

    杨鹏伟
  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • 二分图最大匹配

    二分图也叫二部图,设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不...

    AngelNH
  • BZOJ 1188: [HNOI2007]分裂游戏(multi-nim)

    Description 聪聪和睿睿最近迷上了一款叫做分裂的游戏。该游戏的规则试:共有n个瓶子,标号为0,1,2.....n-1,第i个瓶子中 装有p[i]颗巧...

    attack
  • AtCoder Beginner Contest 181 A ~ E

    D.题意:就是给你一个字符串,让你判断其不同排序是否为能够整除8。能的话就输出“Yes”,否则就输出“No”。

    杨鹏伟
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津

扫码关注云+社区

领取腾讯云代金券