本文主要是介绍HDU - 3518 Boring counting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题面
http://acm.hdu.edu.cn/showproblem.php?pid=3518
2.题意
给你一个字符串,要求你找出一个字符串中出现了至少两次而且互相不重叠的子串的个数
3.思路
建立height数组之后,枚举长度,记录每组中height数组sa[i]的最大值和最小值,只要最大值和最小值之差大于k就可以了
4.代码
/*****************************************************************> File Name: cpp_acm.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: Wed 10 Aug 2016 09:49:47 CST
*****************************************************************/
# include <cstdio>
# include <cstring>
# include <cctype>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;# define rep(i,a,b) for (i=a;i<=b;i++)
# define rrep(i,a,b) for (i=b;i>=a;i--)struct QuickIO{QuickIO(){const int SZ = 1<<20;setvbuf(stdin ,new char[SZ],_IOFBF,SZ);setvbuf(stdout,new char[SZ],_IOFBF,SZ);} //*From programcaicai*//
}QIO;template<class T>void PrintArray(T* first,T* last,char delim=' '){for (;first!=last;first++) cout << *first << (first+1==last?'\n':delim);
}const int debug = 1;
const int size = 10 + 10000000 ;
const int INF = INT_MAX>>1;
typedef long long ll;/*
1.see the size of the input data before you select your algorithm
2.cin&cout is not recommended in ACM/ICPC
3.pay attention to the size you defined, for instance the size of edge is double the size of vertex
*/const int MAXN = 500000 + 1000;
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[MAXN*3],wb[MAXN*3],wv[MAXN*3],wss[MAXN*3]; int c0(int *r,int a,int b){ return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];
} int c12(int k,int *r,int a,int b){ if(k == 2) return r[a] < r[b] || ( r[a] == r[b] && c12(1,r,a+1,b+1) ); else return r[a] < r[b] || ( r[a] == r[b] && wv[a+1] < wv[b+1] );
} void sort(int *r,int *a,int *b,int n,int m){ int i; for(i = 0;i < n;i++)wv[i] = r[a[i]]; for(i = 0;i < m;i++)wss[i] = 0; for(i = 0;i < n;i++)wss[wv[i]]++; for(i = 1;i < m;i++)wss[i] += wss[i-1]; for(i = n-1;i >= 0;i--) b[--wss[wv[i]]] = a[i];
} void dc3(int *r,int *sa,int n,int m){ int i, j, *rn = r + n; int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p; r[n] = r[n+1] = 0; for(i = 0;i < n;i++)if(i %3 != 0)wa[tbc++] = i; sort(r + 2, wa, wb, tbc, m); sort(r + 1, wb, wa, tbc, m); sort(r, wa, wb, tbc, m); for(p = 1, rn[F(wb[0])] = 0, i = 1;i < tbc;i++) rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p - 1 : p++; if(p < tbc)dc3(rn,san,tbc,p); else for(i = 0;i < tbc;i++)san[rn[i]] = i; for(i = 0;i < tbc;i++) if(san[i] < tb)wb[ta++] = san[i] * 3; if(n % 3 == 1)wb[ta++] = n - 1; sort(r, wb, wa, ta, m); for(i = 0;i < tbc;i++)wv[wb[i] = G(san[i])] = i; for(i = 0, j = 0, p = 0;i < ta && j < tbc;p++) sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++]; for(;i < ta;p++)sa[p] = wa[i++]; for(;j < tbc;p++)sa[p] = wb[j++];
}
//str和sa也要三倍 void da(int str[],int sa[],int rrank[],int height[],int n,int m)
{ for(int i = n;i < n*3;i++) str[i] = 0; dc3(str, sa, n+1, m); int i,j,k = 0; for(i = 0;i <= n;i++)rrank[sa[i]] = i; for(i = 0;i < n; i++) { if(k) k--; j = sa[rrank[i]-1]; while(str[i+k] == str[j+k]) k++; height[rrank[i]] = k; }
} int sa[MAXN],rrank[MAXN],height[MAXN]; int n,k; int str[MAXN],len;
char s[MAXN]; void Debug(int n){ for (int i=1;i<=n;i++){ cout << "*" << i << "*\t" << height[i] << "\t";PrintArray(str+sa[i],str+n,'\t'); }
} int main()
{int i,j;while (scanf("%s",s)){if (s[0]=='#') break;for (n=0;s[n]!='\0';n++) str[n] = s[n];//# void da(int str[],int sa[],int rrank[],int height[],int n,int m) da(str,sa,rrank,height,n,250);int cnt = 0;for (k=1;k<=n;k++){int mi = INF, ma = -INF;for (i=1;i<=n;i++){if (height[i] >= k){ma = max(sa[i],ma);mi = min(sa[i],mi);}else {if (ma - mi >= k) cnt++;mi = ma = sa[i];}}if (ma - mi >= k) cnt++;}printf("%d\n",cnt);}return 0;
}这篇关于HDU - 3518 Boring counting的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
