http://acm.hdu.edu.cn/showproblem.php?pid=5769
首先回顾一下以前的，只求不同子串的个数的题目。
比如是：abba
那么
以a为开始的字符串有a, ab, abb, abba
以b为开始的字符串有b, bb, bba
以b开始的字符串有, b, ba
以a开始的有， a
那么因为以i开始的字符串有lenstr - i + 1个，然后可能有相同的，就是以前已经加过了的，就是要减去height[i]。就是答案。
然后这题，变形了一下。还是做出来了，因为是自己想的，思路清晰（debug比较方便），然后出了些样例有错（很幸运找到这样的样例），好开心，我要的就是自己解题而不是抄题解。加油~
考虑至少要有一个a的时候，那么bba, bb, b这里只有一个成立，那么我找到离他最近的那一个a，然后两个位置相减就是不满足题目的数目，这部分应该删除，然后可能会重复，就是上一次已经算过了，所以要和height[i]比较，取最大值减去即可。
不能只减相对位置或者只减height[i]或者两个都减，因为他们是有重叠部分的。
比如abba，求a的字符的时候，第一个b，有b, bb, bba，第二个，有b和ba。然后height[i] = 1，是减去b的，但是相对位置要减去的是2，这个时候，只能取最大值了。因为相对位置包含了height[i]
5
a
abc
b
bbb
b
abba
a
ababc
a
abba
还有这题记得用LL
2e10爆了
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e6 + 20; char str[maxn]; int f; int sa[maxn], x[maxn], y[maxn], book[maxn]; //book[]大小起码是lenstr，book[rank[]] bool cmp(int r[], int a, int b, int len) { //这个必须是int r[] return r[a] == r[b] && r[a + len] == r[b + len]; } void da(char str[], int sa[], int lenstr, int mx) { int *fir = x, *sec = y, *ToChange; for (int i = 0; i <= mx; ++i) book[i] = 0; //清0 for (int i = 1; i <= lenstr; ++i) { fir[i] = str[i]; //开始的rank数组，只保留相对大小即可，开始就是str[] book[str[i]]++; //统计不同字母的个数 } for (int i = 1; i <= mx; ++i) book[i] += book[i - 1]; //统计 <= 这个字母的有多少个元素 for (int i = lenstr; i >= 1; --i) sa[book[fir[i]]--] = i; // <=str[i]这个字母的有x个，那么，排第x的就应该是这个i的位置了。 //倒过来排序，是为了确保相同字符的时候，前面的就先在前面出现。 //p是第二个关键字0的个数 for (int j = 1, p = 1; p <= lenstr; j <<= 1, mx = p) { //字符串长度为j的比较 //现在求第二个关键字，然后合并（合并的时候按第一关键字优先合并） p = 0; for (int i = lenstr - j + 1; i <= lenstr; ++i) sec[++p] = i; //这些位置，再跳j格就是越界了的，所以第二关键字是0，排在前面 for (int i = 1; i <= lenstr; ++i) if (sa[i] > j) //如果排名第i的起始位置在长度j之后 sec[++p] = sa[i] - j; //减去这个长度j，表明第sa[i] - j这个位置的第二个是从sa[i]处拿的，排名靠前也//正常，因为sa[i]排名是递增的 //sec[]保存的是下标，现在对第一个关键字排序 for (int i = 0; i <= mx; ++i) book[i] = 0; //清0 for (int i = 1; i <= lenstr; ++i) book[fir[sec[i]]]++; for (int i = 1; i <= mx; ++i) book[i] += book[i - 1]; for (int i = lenstr; i >= 1; --i) sa[book[fir[sec[i]]]--] = sec[i]; //因为sec[i]才是对应str[]的下标 //现在要把第二关键字的结果，合并到第一关键字那里。同时我需要用到第一关键//字保存的记录，所以用指针交换的方式达到快速交换数组中的值 ToChange = fir; fir = sec; sec = ToChange; fir[sa[1]] = 0; //固定的是0 因为sa[1]固定是lenstr那个0 p = 2; for (int i = 2; i <= lenstr; ++i) //fir是当前的rank值，sec是前一次的rank值 fir[sa[i]] = cmp(sec, sa[i - 1], sa[i], j) ? p - 1 : p++; } return ; } int height[maxn], RANK[maxn]; void CalcHight(char str[], int sa[], int lenstr) { for (int i = 1; i <= lenstr; ++i) RANK[sa[i]] = i; //O(n)处理出rank[] int k = 0; for (int i = 1; i <= lenstr - 1; ++i) { //最后一位不用算，最后一位排名一定是1，然后sa[0]就尴尬了 k -= k > 0; int j = sa[RANK[i] - 1]; //排名在i前一位的那个串，相似度最高 while (str[j + k] == str[i + k]) ++k; height[RANK[i]] = k; } return ; } int pos[maxn]; void work() { char ch[2]; scanf("%s", ch); scanf("%s", str + 1); int lenstr = strlen(str + 1); str[lenstr + 1] = '$'; str[lenstr + 2] = ' '; int lenpos = 0; for (int i = 1; i <= lenstr; ++i) { if (str[i] == ch[0]) { pos[++lenpos] = i; } } LL ans = 0; da(str, sa, lenstr + 1, 128); CalcHight(str, sa, lenstr + 1); for (int i = 2; i <= lenstr + 1; ++i) { if (sa[i] > pos[lenpos]) continue; int add = lenstr - sa[i] + 1; int cut1 = height[i]; int t = lower_bound(pos + 1, pos + 1 + lenpos, sa[i]) - pos; int cut2 = pos[t] - sa[i]; add -= max(cut1, cut2); ans += add; } printf("Case #%d: %I64d ", ++f, ans); } int main() { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }