题目链接:uva 10829 - L-Gap Substrings
题目大意:给定一个字符串,问有多少字符串满足UVU的形式,要求U非空,V的长度为g。
解题思路;对字符串的正序和逆序构建后缀数组,然后枚举U的长度l,每次以长度l分区间,在l和l+d+g所在的两个区间上确定U的最大长度。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100005;
struct Suffix_Arr {
int n, len, s[maxn];
int SA[maxn], rank[maxn], ......
阅读全文