分类 - 字符串算法

? 解题记录 ? ? 数学 ?    2020-11-01 12:13:03    975    0    0
https://ac.nowcoder.com/acm/contest/7502/J 题目大意: 定义串 S1=[1]Sm=Sm−1+[m]+Sm−1" role="presentation" style="width: 100%; position: relative;">S1=[1]Sm=Sm−1+[m]+Sm−1S1=[1]Sm=Sm−1+[m]+Sm−1 S^1=[1]\\ S^m=S^{m-1}+[m]+S^{m-1} 其中′+′" role="presentation"
? 解题记录 ? ? 哈希 ?    2020-11-01 12:03:11    1049    0    0
https://ac.nowcoder.com/acm/contest/7502/G 题目大意: 给定一个长度为n" role="presentation" style="position: relative;">nnn数组,每一次可以进行如下操作: 1、将数组划分为前后两段 2、将这两段分别翻转 问最后可能得到多少种数组? 多组数据 Σn≤2×106" role="presentation" style="position: relative;">Σn≤2×106Σn≤2×106\Sigma
? 解题记录 ? ? POJ ? ? 后缀数组 ? ? ST表 ?    2018-12-10 08:34:41    662    0    0
Description The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1. Given a string containing lowercase letters, you are
? 解题记录 ? ? SPOJ ? ? 后缀数组 ?    2018-12-05 23:04:22    441    0    0
后缀数组模板题,直接看注释就好了 #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int maxn = 1e5 + 5; char s[maxn]; LL ans; int SA[maxn], SA2[maxn], RK[maxn], tot[maxn], H[maxn]; //SA : 第一关键字排名为i的开头下标 //SA2 : 第二关键字排名为i的开头下标 //RK : 原字符串中下标为i后缀的
? 解题记录 ? ? BZOJ ? ? FFT|NTT ?    2018-09-20 14:56:12    906    0    0
DescriptionByteasar 组建了一支舰队!他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图,其中有些位置是“ .”,表示这一格是海水,可以通过;有些位置是“#”,表示这一格是礁石,不可以通过;有些位置是“o”,表 示这一格目前有一艘舰,且舰离开这一格之后,这一格将变为“.”。这些“o” 表示Byteasar 的舰队,他们每天 可以往上下左右中的一个方向移动一格,但不能有任何一艘舰驶出地图。特别地,Byteasar 对阵形有所研究,所 以他不希望在航行的过程中改变阵形,即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以 航行无限长的时间,每当一艘
? 解题记录 ? ? BZOJ ? ? FFT|NTT ? ? 构造 ?    2018-09-19 08:03:56    642    0    0
【题目描述】兔子们在玩两个串的游戏。给定两个字符串S和T,兔子们想知道T在S中出现了几次,分别在哪些位置出现。注意T中可能有“?”字符,这个字符可以匹配任何字符。 【输入】两行两个字符串,分别代表S和T 【输出】第一行一个正整数k,表示T在S中出现了几次 接下来k行正整数,分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出,S下标从0开始。 【输入样例】bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab a?aba?abba 【输出样例】
? 解题记录 ? ? Codeforces ? ? KMP ? ? 动态规划 ?    2018-09-18 09:18:41    474    0    0
You are given a binary string s" data-mce-tabindex="0">ss. Find the number of distinct cyclical binary strings of length n" data-mce-tabindex="0">nn which contain s" data-mce-tabindex="0">ss as a substring. The cyclical string t" data-mce-tabindex="0"
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could b
? 解题记录 ? ? 后缀自动机 ? ? Splay ?    2018-07-24 17:51:37    336    0    0
Description懒得写背景了,给你一个字符串init,要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符串s在当前字符串中出现了几次?(作为连续子串) 你必须在线支持这些操作。 Input第一行一个数Q表示操作个数 第二行一个字符串表示初始字符串init 接下来Q行,每行2个字符串Type,Str Type是ADD的话表示在后面插入字符串。 Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。 为了体现在线操作,你需要维护一个变量mask,初始值为0       读入串Str之后,使用这个过程将之解码成真
? 解题记录 ? ? Atcoder ? ? 动态规划 ? ? 构造 ?    2018-07-15 11:00:04    740    0    0
    Problem StatementTaichi thinks a binary string X of odd length N is beautiful if it is possible to apply the following operation  N−12 times so that the only character of the resulting string is 1 :  Choose three consecutive&n