题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3518
数据生成器:http://paste.ubuntu.com/18021072/
这个,我是SA乱搞,时间复杂度O(n^3)QAQ,不过要把我卡到这个时间复杂度的数据貌似不好出
还是说说正解吧:枚举长度,然后height[]数组分组搞一搞,又是论文题QAQ
其实最开始想的是SAM,每个节点记录一个最先出现的位置和最后出现的位置,而且这样的话,貌似可以做到O(n)
但是懒得写啦! 还是上一个SA的乱搞代码就水过了吧!
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 3000+9; char pat[MAXN]; int n; namespace Suffix_Array{ #define SA Suffix_Array #define SIGMA_SIZE 26 int sa[MAXN],bot[MAXN],*tmp,*rank; int t1[MAXN],t2[MAXN],height[MAXN],m; inline void GetHeight(){ for (int i=1,t,p1,p2;i<=n;i++)if(rank[i]>1){ t = max(0,height[rank[i-1]]-1); p1 = i+t; p2 = sa[rank[i]-1]+t; while (pat[p1++]==pat[p2++]) t++; height[rank[i]] = t; } } inline void build(){ memset(sa,0,sizeof(sa)); memset(t1,0,sizeof(t1)); memset(t2,0,sizeof(t2)); memset(height,0,sizeof(height)); memset(bot,0,sizeof(bot)); tmp = t1; rank = t2; n = strlen(pat+1); m = SIGMA_SIZE; for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+1]++; for (int i=2;i<=m;i++) bot[i] += bot[i-1]; for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i; m = rank[sa[1]] = 1; for (int i=2;i<=n;i++) rank[sa[i]] = (tmp[sa[i]]==tmp[sa[i-1]])?m:++m; for (int k=1;k<=n;k*=2){int T=0; for (int i=n-k+1;i<=n;i++) tmp[++T] = i; for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k; for (int i=1;i<=m;i++) bot[i] = 0; for (int i=1;i<=n;i++) bot[rank[i]]++; for (int i=2;i<=m;i++) bot[i] += bot[i-1]; for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i]; swap(rank, tmp); m = rank[sa[1]] = 1; for (int i=2;i<=n;i++) if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]]=m; else rank[sa[i]] = ++m; if (m >= n) break; } GetHeight(); } inline bool judge(int w, int len){ int mn=sa[w]-len, mx=sa[w]+len; while (w < n && height[w+1]>=len) if (sa[++w] <= mn || sa[w] >= mx) return true; return false; } inline void solve(){ int vout = 0; for (int i=1;i<=n;i++){ int len=n-sa[i]-height[i]+1; for (int j=len;j;j--) if (judge(i,j+height[i])) {vout += j; break;} } printf("%d\n",vout); } }; int main(){ while (~scanf("%s",pat+1) && pat[1] != '#'){ SA::build(); SA::solve(); } return 0; }