题目链接: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], height[maxn];
int tmp_one[maxn], tmp_two[maxn], c[30];
int d[maxn][20];
void init(char* str);
void build_arr(int m);
void get_height();
void rmq_init();
int rmq_query(int l, int r);
ll solve(int m);
void put();
}AC;
char str[maxn];
int main () {
int cas, n;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
scanf("%d%s", &n, str);
AC.init(str);
printf("Case %d: %lld\n", i, AC.solve(n));
}
return 0;
}
void Suffix_Arr::put () {
for (int i = 0; i < n; i++)
printf("%d ", SA[i]);
printf("\n");
for (int i = 0; i < n; i++)
printf("%d ", height[i]);
printf("\n");
}
ll Suffix_Arr::solve(int m) {
build_arr(28);
get_height();
rmq_init();
ll ret = 0;
for (int l = 1; l < len / 2; l++) {
for (int i = 0; i < len; i += l) {
int j = i + l + m, sum = 0;
if (j < len)
sum += min(rmq_query(rank[i], rank[j]), l);
if (i)
sum += min(rmq_query(rank[n-i-1], rank[n-j-1]), l-1);
ret += max(0, sum - l + 1);
}
}
return ret;
}
int Suffix_Arr::rmq_query(int l, int r) {
if (l > r) swap(l, r);
l++;
int k = 0;
while ((1<<(k+1)) <= r - l + 1) k++;
return min(d[l][k], d[r - (1<<k) + 1][k]);
}
void Suffix_Arr::rmq_init() {
for (int i = 0; i < n; i++) d[i][0] = height[i];
for (int k = 1; (1<<k) <= n; k++) {
for (int i = 0; i + (1<<k) - 1 < n; i++)
d[i][k] = min(d[i][k-1], d[i+(1<<(k-1))][k-1]);
}
}
void Suffix_Arr::init(char* str) {
n = 0;
len = strlen(str);
for (int i = 0; i < len; i++)
s[n++] = str[i] - 'a' + 1;
s[n++] = 27;
for (int i = len - 1; i >= 0; i--)
s[n++] = str[i] - 'a' + 1;
s[n++] = 0;
}
void Suffix_Arr::get_height() {
for (int i = 0; i < n; i++)
rank[SA[i]] = i;
int mv = height[0] = 0;
for (int i = 0; i < n - 1; i++) {
if (mv) mv--;
int j = SA[rank[i] - 1];
while (s[i+mv] == s[j+mv])
mv++;
height[rank[i]] = mv;
}
}
void Suffix_Arr::build_arr(int m) {
int *x = tmp_one, *y = tmp_two;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i-1];
for (int i = n-1; i >= 0; i--) SA[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1) {
int mv = 0;
for (int i = n - k; i < n; i++) y[mv++] = i;
for (int i = 0; i < n; i++) if (SA[i] >= k)
y[mv++] = SA[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 1; i < m; i++) c[i] += c[i-1];
for (int i = n-1; i >= 0; i--) SA[--c[x[y[i]]]] = y[i];
swap(x, y);
mv = 1;
x[SA[0]] = 0;
for (int i = 1; i < n; i++)
x[SA[i]] = (y[SA[i-1]] == y[SA[i]] && y[SA[i-1] + k] == y[SA[i] + k] ? mv - 1 : mv++);
if (mv >= n)
break;
m = mv;
}
}
分享到:
相关推荐
去食谱 来源,一个社区为现实世界的 Golang 开发构建并贡献了实用食谱的集合,由支持。 贡献 Go Cookbook 由支持,但由社区构建,因此非常... - title: Detecting All Substrings path: false 指定wip: true将“[正在
Suffix trees have numerous applications, often providing linear-time solutions to challenging string ...Common substrings, with applications Matching statistics Suffix arrays Genome-scale projects
附加的功能: -给定任何长度L,以使0 <= L <= n,该算法将在O(n)时间内按字典顺序确定S的长度L的最后一个子串。 -该算法可以确定在O(n)时间内所有长度<= n的S的字典顺序上的S子字符串。 这是通过为每...
substrings (i.e. left substring and right substring). The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring. Example 1: Input: ...
试题 算法提高 Substrings 问题描述 You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring...
Matching and extraction of matches / substrings from the source text. Searching for regular expressions within streams and memory buffers. To search within streams or files (of virtually unlimited ...
-02.04 连续字符串02.05 计算表达式-02.05 平均Step-02.05 一位数字-02.05 https://www.codewars.com/kata/单位数非偶数子字符串02.06 https://www.codewars.com/kata/non-even-substrings 未知数量的重复项。...
You are visitor as of October 17, 1996. The Art of Assembly Language Programming <br>Forward Why ... Conditional Jump Instructions II <br> 6.12 Laboratory Exercises 6.12.1 The IBM/L System...
Matching and extraction of matches / substrings from the source text. Searching for regular expressions within streams and memory buffers. To search within streams or files (of virtually unlimited ...
What You Will Learn Formulate an expression Work with arbitrary char classes, ... Handle substring extraction from regex using Perl 6 capture groups, capture substrings, and reuse substrings
塞雷娅和后缀 栗山未来的石头 狗狗变色 第十二天 条纹 第十三天 节日晚会 第十四天 Karen_and_Coffee 第十六天 Sam_and_substrings 第18天 培养细菌 第19天 费多和新游戏 第20天 夏季抛售 第21天 最小三进制...
Matching and extraction of matches / substrings from the source text. Searching for regular expressions within streams and memory buffers. To search within streams or files (of virtually unlimited ...
Substrings * Problem URL : https://leetcode.com/problems/palindromic-substrings/ * Date : Oct 17 2017 * Complexity : O(n^3) Time, O(n) space * Author : Atiq Rahman * Status : Accepted * Notes : Track ...
create and use strings and substrings, and see the various common operations available for strings. Lesson 6, Functional Programming and Lazy Operations, ventures at functional programming and ...
List Slicing and Substrings x elif ("Else If") Statements x And that's it! x Dictionaries x Sets of Words for Hangman x Chapter 6 - Tic Tac Toe x Source Code x Designing the Program x Game AI x ...
================ LeetCode ================动态编程1.... Palindromic Substrings [647]9. Maximum Length of Pair Chain [646]10. Integer Break [343]11. Count Numbers with Unique Digits [357]12. 2-Key
Java Program To Find All Substrings Of A String
分组, , , , , , , , , , , , ,前瞻和回顾间谍, 偷看, 可寻加窗windowed , 子字符串, substrings_indexes , 交错, windowed_complete , 成对增广count_cycle , 散布, 填充, mark_ends , ...
3.10 Accessing Substrings 3.11 Changing the Indentation of a Multiline String 3.12 Testing Whether a String Represents an Integer 3.13 Expanding and Compressing Tabs 3.14 Replacing Multiple ...
For instance, size filters (width, height), URL filters (include, exclude substrings), address name filter (name wildcard) and others. With GetWebPics you can download various types of pictures, ...