北京网站制作公司建站,博物馆网站建设经验,如何恢复网站,wordpress主题制作器【链接】h在这里写链接 【题意】 接上一篇文章【题解】 一个字符串所有不同的子串的个数∑(len-sa[i]-height[i])【错的次数】 0【反思】 在这了写反思【代码】 #includebits/stdc.h
using namespace std;const int N 2e3;
const int MAX_CHAR 300;//每个数字的最大… 【链接】h在这里写链接 【题意】 接上一篇文章 【题解】 一个字符串所有不同的子串的个数∑(len-sa[i]-height[i]) 【错的次数】 0 【反思】 在这了写反思 【代码】 #includebits/stdc.h
using namespace std;const int N 2e3;
const int MAX_CHAR 300;//每个数字的最大值。
char s[N 10];//如果是数字,就写成int s[N10]就好,从0开始存
int Sa[N 10], T1[N 10], T2[N 10], C[N 10];
int Height[N 10], Rank[N 10];void build_Sa(int n, int m) {int i, *x T1, *y T2;for (i 0; im; i) C[i] 0;for (i 0; in; i) C[x[i] s[i]];for (i 1; im; i) C[i] C[i - 1];for (i n - 1; i 0; i--) Sa[--C[x[i]]] i;for (int k 1; k n; k 1){int p 0;for (i n - k; in; i) y[p] i;for (i 0; in; i) if (Sa[i] k) y[p] Sa[i] - k;for (i 0; im; i) C[i] 0;for (i 0; in; i) C[x[y[i]]];for (i 1; im; i) C[i] C[i - 1];for (i n - 1; i 0; i--) Sa[--C[x[y[i]]]] y[i];swap(x, y);p 1; x[Sa[0]] 0;for (i 1; in; i)x[Sa[i]] y[Sa[i - 1]] y[Sa[i]] y[Sa[i - 1] k] y[Sa[i] k] ? p - 1 : p;if (p n) break;m p;}
}void getHeight(int n)
{int i, j, k 0;for (i 1; i n; i) Rank[Sa[i]] i;for (i 0; in; i) {if (k) k--;j Sa[Rank[i] - 1];while (s[i k] s[j k]) k;Height[Rank[i]] k;}
}int bo[300];int main() {//freopen(F:\\rush.txt, r, stdin); int T;scanf(%d, T);while (T--){scanf(%s, s);int n strlen(s), tn n;s[n] 0;build_Sa(n 1, MAX_CHAR);//注意调用n1 getHeight(n);int ans 0;for (int i 1; i n; i)ans (n - Height[i] - Sa[i]);printf(%d\n, ans);}return 0;
} 转载于:https://www.cnblogs.com/AWCXV/p/7625984.html
