码农场
子串函数和：求字符串的所有子串出现次数n代入n(n+1)/2之和。
4.7华丽地处理字符串
后缀数组
题目有些绕，直白地讲就是枚举所有不同的子串，求出现次数，代入该表达式求和。枚举子串的通用做法是，高度数组连续一段不小于h的区间长度代表长h的子串的出现次数。将高度数组视作x轴上宽度为1，高度为height[i]的矩形序列的话，出现次数就是求高度大于h的最宽矩形。
这种问题的求法也有定式，就是类似书上栈的那节用单调栈的做法。定义一个公共前缀长度height的非严格递增栈。
每次插入height[i]时弹出的那些元素end与i共同构成“最宽矩形”的始末区间，所以矩形宽度为i-end。这些矩形的高度就对应着一个子串。
进一步，若子串A包含子串B，则说明有A.length-B.length个长B.length的子串出现次数都是i-end。如果某后缀的长度比当前height大，后缀的height也比当前height大，该公共前缀就包含当前公共前缀，就会发生这种情况了。
子串个数乘以f(子串出现次数)，累加到答案上即可。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX_N = 100100;
struct SuffixArray
{
int sa[MAX_N], height[MAX_N];
void build(const string &s)
{ build(s.c_str(), s.size()); }
void build(const char *t, int n)
{
// suffix array
static int g[MAX_N], b[MAX_N];
for (int i = 0; i < n + 1; ++i)
{
sa[i] = i, g[i] = t[i];
}
b[0] = b[n] = 0;
sort(sa, sa + n + 1, SAComp(0, g));
for (int h = 1; b[n] != n; h *= 2)
{
SAComp comp(h, g);
sort(sa, sa + n + 1, comp);
for (int i = 0; i < n; ++i)
{
b[i + 1] = b[i] + comp(sa[i], sa[i + 1]);
}
for (int i = 0; i < n + 1; ++i)
{
g[sa[i]] = b[i];
}
}
// longest common prefix (you can omit here)
for (int i = 0; i < n + 1; ++i)
{
b[sa[i]] = i;
}
int h = 0;
for (int i = 0; i < n; ++i)
{
const int j = sa[b[i] - 1];
while (j + h < n && i + h < n && t[j + h] == t[i + h])
h++;
height[b[i]] = h;
if (h)
h--;
}
height[0] = -1;
}
struct SAComp
{
const int h, *g;
SAComp(int h, int *g) : h(h), g(g)
{}
bool operator()(int l, int r)
{
return g[l] != g[r] ? g[l] < g[r] : g[l + h] < g[r + h];
}
};
} sa;
char buf[MAX_N];
long long cnt(long long n)
{
return n * (n + 1) / 2;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("err.txt", "w", stderr);
#endif
int n;
long long ans;
vector<pair<pair<int, int>, int>> v;//单调栈
scanf("%s", buf);
n = (int) strlen(buf);
sa.build(buf, n);
sa.height[n + 1] = 0;
sa.sa[n + 1] = n;
ans = 0;
for (int i = 1; i <= n + 1; ++i)
{
while (!v.empty() && v.back().first.second > sa.height[i])
{
auto &end = v.back();// 某子串出现i-end.second次
if (end.first.first < sa.height[i])//队尾公共前缀长度小于当前公共前缀长度
{// 有（end.公共前缀长度减去当前公共前缀长度）种子串
ans += (end.first.second - sa.height[i]) * cnt(i - end.second);
end.first.second = sa.height[i];//维护非严格单调增栈
}
else
{
ans += (end.first.second - end.first.first) * cnt(i - end.second);
v.pop_back();//维护非严格单调增栈
}
}
v.push_back({{sa.height[i], n - sa.sa[i]}, i});
}
printf("%lld\n", ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stderr);
#endif
return 0;
}
Reference
译者的代码：https://searchcode.com/codesearch/view/30101319/
知识共享署名-非商业性使用-相同方式共享：码农场 » Codeforces 123D String 题解《挑战程序设计竞赛》