公司建设网站制作建设教育协会官网

当前位置： 首页 > news >正文

公司建设网站制作,建设教育协会官网,wordpress tinymce advanced,成都 网站建设培训目录 前缀函数应用【模板】KMP题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示样例 1 解释数据规模与约定 思路AC代码 本质不同子串数 例题讲解[NOI2014] 动物园题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路AC代码 [POI2006] OKR-Periods of … 目录 前缀函数应用【模板】KMP题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示样例 1 解释数据规模与约定 思路AC代码 本质不同子串数 例题讲解[NOI2014] 动物园题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路AC代码 [POI2006] OKR-Periods of Words题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 思路AC代码 [BOI2009] Radio Transmission 无线传输题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示样例输入输出 1 解释规模与约定 思路AC代码 [COCI2011-2012#4] KRIPTOGRAM题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示思路AC代码 为方便讲述字符串下标从 开始 前缀函数 给定一个长度为 n n n的字符串 s s s其前缀函数定义为一个长度为 n n n的数组 π \pi π, π i \pi_i πi​ 为子串 s [ 0 , 1 , … … i ] s[0,1,……i] s[0,1,……i]的所有相等的真前缀和真后缀称为border的最长长度若没有则为. 朴素求解前缀函数 int n (int)s.length(); vectorint pi(n); for (int i 1; i n; i) for (int j i; j 0; j–) if (s.substr(0, j) s.substr(i - j 1, j)) {pi[i] j;break; }这显然是一个 n 3 n^3 n3的算法 我们可以通过一些观察来优化这个算法。 π i 1 ≤ π i 1 \pi _{i1} \leq \pii 1 πi1​≤πi​1 反证即可假设 π i 1 \pi{i1} πi1​更大那 π i \pi_i πi​也应该更大 通过这个我们可以把原来的暴力优化成 但这还不够优秀如果失配我们可以利用之前已经处理过的信息来避免一些重复比较 考虑我们当前已经处理完前 i i i为且第 i 1 i1 i1位失配即 s i ≠ s π i 1 si\neq s{\pii1} si​sπi​1​我们想快速找到最长的新匹配。 由 border 的定义也就是我们要找到最大的j使得 s i , j s i j 1 , i s{i,j}s{ij1,i} si,j​sij1,i​^ s j 1 s i 1 s{j1}s{i1} sj1​si1​ 只考虑第一个条件事实上 j π π i j\pi{\pii} jππi​​ 证明 π π i \pi{\pii} ππi​​满足条件1 手模一下即可。 π π i \pi{\pi_i} ππi​​是最大的满足条件的反证即可。 通过以上两个观察我们就可以得出最终的算法也就是 KMP for(int i 2, j 0; i n; i){ while(j s[j 1] ! s[i])j nxt[j]; if(s[j 1] s[i]) j; nxt[i] j; }时间复杂度由 while 循环计算复杂度 O ( n ) O(n) O(n) 应用 字符串匹配 【模板】KMP 题目描述 给出两个字符串 s 1 s_1 s1​ 和 s 2 s_2 s2​若 s 1 s_1 s1​ 的区间 [ l , r ] [l, r] [l,r] 子串与 s 2 s_2 s2​ 完全相同则称 s 2 s_2 s2​ 在 s 1 s_1 s1​ 中出现了其出现位置为 l l l。 现在请你求出 s 2 s_2 s2​ 在 s 1 s_1 s1​ 中所有出现的位置。 定义一个字符串 s s s 的 border 为 s s s 的一个非 s s s 本身的子串 t t t满足 t t t 既是 s s s 的前缀又是 s s s 的后缀。 对于 s 2 s_2 s2​你还需要求出对于其每个前缀 s ′ s s′ 的最长 border t ′ t t′ 的长度。 输入格式 第一行为一个字符串即为 s 1 s_1 s1​。 第二行为一个字符串即为 s 2 s_2 s2​。 输出格式 首先输出若干行每行一个整数按从小到大的顺序输出 s 2 s_2 s2​ 在 s 1 s_1 s1​ 中出现的位置。 最后一行输出 ∣ s 2 ∣ |s_2| ∣s2​∣ 个整数第 i i i 个整数表示 s 2 s_2 s2​ 的长度为 i i i 的前缀的最长 border 长度。 样例 #1 样例输入 #1 ABABABC ABA样例输出 #1 1 3 0 0 1提示 样例 1 解释 。 对于 s 2 s_2 s2​ 长度为 3 3 3 的前缀 ABA字符串 A 既是其后缀也是其前缀且是最长的因此最长 border 长度为 1 1 1。 数据规模与约定 本题采用多测试点捆绑测试共有 3 个子任务。 Subtask 130 points ∣ s 1 ∣ ≤ 15 |s_1| \leq 15 ∣s1​∣≤15 ∣ s 2 ∣ ≤ 5 |s_2| \leq 5 ∣s2​∣≤5。Subtask 240 points ∣ s 1 ∣ ≤ 1 0 4 |s_1| \leq 10^4 ∣s1​∣≤104 ∣ s 2 ∣ ≤ 1 0 2 |s_2| \leq 10^2 ∣s2​∣≤102。Subtask 330 points无特殊约定。 对于全部的测试点保证 1 ≤ ∣ s 1 ∣ , ∣ s 2 ∣ ≤ 1 0 6 1 \leq |s_1|,|s_2| \leq 10^6 1≤∣s1​∣,∣s2​∣≤106 s 1 , s 2 s_1, s_2 s1​,s2​ 中均只含大写英文字母。 思路 对模式串跑 KMP得到 数组ne然后直接扫文本串匹配即可若失配则跳 完全匹配时也跳 因为有可能两次出现有重叠的部分。 AC代码 #includebits/stdc.h using namespace std; const int N1000010; int n,m,i,j; char p[N],s[N]; int ne[N]; int main(){scanf(%s%s,s1,p1);mstrlen(s1);nstrlen(p1);for(i2,j0;in;i){while(jp[i]!p[j1])jne[j];if(p[i]p[j1])j;ne[i]j;}for(i1,j0;im;i){while(js[i]!p[j1])jne[j];if(s[i]p[j1])j;if(jn){printf(%d\n,i-n1);jne[j];}}for(int i1;in;i)printf(%d ,ne[i]); } 本质不同子串数 给定长度为 n n n的字符串 s 求本质不同子串数。考虑用递推的方法令 s求本质不同子串数。 考虑用递推的方法令 s求本质不同子串数。考虑用递推的方法令 f i fi fi​为 s [ 1 , i ] s[1,i] s[1,i]的本质不同子串数考虑如何算出 f i 1 f{i1} fi1​新出现的子串显然只能是以 i 1 i1 i1结尾的。 如果将字符串反转就变成要计数以 i 1 i1 i1开头且未出现过的子串。 我们可以反过来计数已经出现过的有多少个考虑我们前缀函数求出了什么每一个border都是一个以 i 1 i1 i1开头的子串的出现。 所以出现过的一共有 π m a x \pi{max} πmax​个新增的就是 i 1 − π m a x i1-\pi{max} i1−πmax​ 这样我们就可以以 O ( 2 ) O(2) O(2)的复杂度求出本质不同子串数。 当然还有更复杂的算法可以用更优秀的复杂度处理该问题在此不表。 例题讲解 [NOI2014] 动物园 题目描述 近日园长发现动物园中好吃懒做的动物越来越多了。例如企鹅只会卖萌向游客要吃的。为了整治动物园的不良风气让动物们凭自己的真才实学向游客要吃的园长决定开设算法班让动物们学习算法。 某天园长给动物们讲解 KMP 算法。 园长“对于一个字符串 S S S它的长度为 L L L。我们可以在 O ( L ) O(L) O(L) 的时间内求出一个名为 n e x t \mathrm{next} next 的数组。有谁预习了 n e x t \mathrm{next} next 数组的含义吗” 熊猫“对于字符串 S S S 的前 i i i 个字符构成的子串既是它的后缀又是它的前缀的字符串中它本身除外最长的长度记作 n e x t [ i ] \mathrm{next}[i] next[i]。” 园长“非常好那你能举个例子吗” 熊猫“例 S S S 为 abcababc \verb!abcababc! abcababc则 n e x t [ 5 ] 2 \mathrm{next}[5]2 next[5]2。因为 S S S的前 5 5 5个字符为 abcab \verb!abcab! abcab ab \verb!ab! ab 既是它的后缀又是它的前缀并且找不到一个更长的字符串满足这个性质。同理还可得出 n e x t [ 1 ] n e x t [ 2 ] n e x t [ 3 ] 0 \mathrm{next}[1] \mathrm{next}[2] \mathrm{next}[3] 0 next[1]next[2]next[3]0 n e x t [ 4 ] n e x t [ 6 ] 1 \mathrm{next}[4] \mathrm{next}[6] 1 next[4]next[6]1 n e x t [ 7 ] 2 \mathrm{next}[7] 2 next[7]2 n e x t [ 8 ] 3 \mathrm{next}[8] 3 next[8]3。” 园长表扬了认真预习的熊猫同学。随后他详细讲解了如何在 O ( L ) O(L) O(L) 的时间内求出 n e x t \mathrm{next} next 数组。 下课前园长提出了一个问题“KMP 算法只能求出 n e x t \mathrm{next} next 数组。我现在希望求出一个更强大 n u m \mathrm{num} num 数组一一对于字符串 S S S 的前 i i i 个字符构成的子串既是它的后缀同时又是它的前缀并且该后缀与该前缀不重叠将这种字符串的数量记作 n u m [ i ] \mathrm{num}[i] num[i]。例如 S S S 为 aaaaa \verb!aaaaa! aaaaa则 n u m [ 4 ] 2 \mathrm{num}[4] 2 num[4]2。这是因为 S S S的前 4 4 4 个字符为 aaaa \verb!aaaa! aaaa其中 a \verb!a! a 和 aa \verb!aa! aa 都满足性质‘既是后缀又是前缀’同时保证这个后缀与这个前缀不重叠。而 aaa \verb!aaa! aaa 虽然满足性质‘既是后缀又是前缀’但遗憾的是这个后缀与这个前缀重叠了所以不能计算在内。同理 n u m [ 1 ] 0 , n u m [ 2 ] n u m [ 3 ] 1 , n u m [ 5 ] 2 \mathrm{num}[1] 0,\mathrm{num}[2] \mathrm{num}[3] 1,\mathrm{num}[5] 2 num[1]0,num[2]num[3]1,num[5]2。” 最后园长给出了奖励条件第一个做对的同学奖励巧克力一盒。听了这句话睡了一节课的企鹅立刻就醒过来了但企鹅并不会做这道题于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出 n u m \mathrm{num} num数组呢 特别地为了避免大量的输出你不需要输出 n u m [ i ] \mathrm{num}[i] num[i] 分别是多少你只需要输出所有 ( n u m [ i ] 1 ) (\mathrm{num}[i]1) (num[i]1) 的乘积对 1 0 9 7 10^9 7 1097 取模的结果即可。 输入格式 第 1 1 1 行仅包含一个正整数 n n n表示测试数据的组数。 随后 n n n 行每行描述一组测试数据。每组测试数据仅含有一个字符串 S S S S S S 的定义详见题目描述。数据保证 S S S 中仅含小写字母。输入文件中不会包含多余的空行行末不会存在多余的空格。 输出格式 包含 n n n 行每行描述一组测试数据的答案答案的顺序应与输入数据的顺序保持一致。对于每组测试数据仅需要输出一个整数表示这组测试数据的答案对 1 0 9 7 10^97 1097 取模的结果。输出文件中不应包含多余的空行。 样例 #1 样例输入 #1 3 aaaaa ab abcababc样例输出 #1 36 1 32提示 测试点编号约定1 n ≤ 5 , L ≤ 50 n \le 5, L \le 50 n≤5,L≤502 n ≤ 5 , L ≤ 200 n \le 5, L \le 200 n≤5,L≤2003 n ≤ 5 , L ≤ 200 n \le 5, L \le 200 n≤5,L≤2004 n ≤ 5 , L ≤ 10 , 000 n \le 5, L \le 10,000 n≤5,L≤10,0005 n ≤ 5 , L ≤ 10 , 000 n \le 5, L \le 10,000 n≤5,L≤10,0006 n ≤ 5 , L ≤ 100 , 000 n \le 5, L \le 100,000 n≤5,L≤100,0007 n ≤ 5 , L ≤ 200 , 000 n \le 5, L \le 200,000 n≤5,L≤200,0008 n ≤ 5 , L ≤ 500 , 000 n \le 5, L \le 500,000 n≤5,L≤500,0009 n ≤ 5 , L ≤ 1 , 000 , 000 n \le 5, L \le 1,000,000 n≤5,L≤1,000,00010 n ≤ 5 , L ≤ 1 , 000 , 000 n \le 5, L \le 1,000,000 n≤5,L≤1,000,000 思路 要求的就是每个前缀的 border 集合大小并且满足这个 border 得是不大于字符串长度一半的。 首先给出一种暴力的做法对于每一个前缀 s [ 1 : j ] s[1:j] s[1:j]都不断跳 next 指针如果当前跳到 i i i的节点 满足其长度不超过 j 2 \frac{j}{2} 2j​ 那么就给 n u m j num_j numj​加上1 。这个算法成立的原因是 border 的传递性不断迭代 next 等价于遍历 border。 集合大小可以通过跳 next 的次数得到也就是说我们可以记录一下从每个串出发不断跳next能跳多少次计为 c n t i cnt_i cnti​ 那么有 c n t i c n t n e x t i 1 cnticnt{next_i}1 cnti​cntnexti​​1 。其实也可以将 ( i , n e x t i ) (i,next_i) (i,nexti​)建成一棵树这棵树常被称为 b o r d e r border border树或是\( f a i l fail fail树。树上的深度也就代表着对应节点的 b o r d e r border border个数。 于是问题可以转化为对于每个 s [ 1 : i ] s[1:i] s[1:i]求满足条件的最长的 border s[1;j]之后给答案累乘上 c n t j 1 cnt_j1 cntj​1即可。 至于如何去求这个 j j j首先给出一种基于分析的做法 如果我们已经求出了 s [ 1 : i ] s[1 : i] s[1:i] 的 j j j 在这个基础上去求 s [ 1 : i 1 ] s[1 : i 1] s[1:i1] 的满足条件的 k k k 。 直觉告诉我们用与求 next 指针一样的方法去做就好了不断去检查 s j 1 s_{j1} sj1​ 是否与 s i 1 s_{i1} si1​相等。如果是那么 k j 1 k j 1 kj1否则令 j n e x t j j next_j jnextj​并继续检测相等的过程。特别的 最终如果发现 k i 1 2 k \frac{i1}{2} k2i1​那么令 k n e x t k k next_k knextk​。 根据与求 next 过程类似的分析可以发现这个过程求出的 j 一定是一个合法的 border。 但是为什么一定是最大的可以通过反证法证明直接理解也并不困难。 另外给出一种看起来就很套路的做法 问题可以转换到 border 树上。那么只需要对于每个前缀s[1 : i]求出border 树上 i 的祖先中长度满足条件 i 2 \frac{i}{2} 2i​ 的第一个并给答案累乘它的深度。 可以通过倍增来求解。预处理出 N e x t x , i Next_{x,i} Nextx,i​表示从s[1 : x]跳 2 i 2^i 2i次 next 指针会跳到哪个节点。 对于每次询问i从大到小枚举二进制位如果跳完之后还不满足 i 2 \frac{i}{2} 2i​ 就不断跳。这个过程与倍增求 lca 类似。 AC代码 #include bits/stdc.h using namespace std; const int mod 1e9 7; char s[1000100]; int f[1000100], num[1000100]; int main() {int T;scanf(%d, T);while (T--) {scanf(%s, s 1);int n strlen(s 1);f[1] 0;num[1] 1;for (int i 2, j 0; i n; i) { while (j s[j 1] ! s[i]) j f[j];if (s[j 1] s[i])f[i] j;elsef[i] 0;num[i] num[j] 1;}long long ans 1;for (int i 2, j 0; i n; i) {while (j s[j 1] ! s[i]) j f[j];if (s[j 1] s[i]) j;if (j i 1) j f[j];ans (ans * (num[j] 1)) % mod;}printf(%lld\n, ans);}return 0; } [POI2006] OKR-Periods of Words 题面翻译 对于一个仅含小写字母的字符串 a a a p p p 为 a a a 的前缀且 p ≠ a p\ne a pa那么我们称 p p p 为 a a a 的 proper 前缀。 规定字符串 Q Q Q 表示 a a a 的周期当且仅当 Q Q Q 是 a a a 的 proper 前缀且 a a a 是 Q Q QQ QQ 的前缀。若这样的字符串不存在则 a a a 的周期为空串。 例如 ab 是 abab 的一个周期因为 ab 是 abab 的 proper 前缀且 abab 是 abab 的前缀。 求给定字符串所有前缀的最大周期长度之和。 题目描述 A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By ABC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that APB. In other words, prefixes of A are the initial fragments of A. In addition, if P!A and P is not an empty string, we say, that P is a proper prefix of A. A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string. Task Write a programme that: reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output. 输入格式 In the first line of the standard input there is one integer k k k ( 1 ≤ k ≤ 1 000 000 1\le k\le 1\ 000\ 000 1≤k≤1 000 000) - the length of the string. In the following line a sequence of exactly k k k lower-case letters of the English alphabet is written - the string. 输出格式 In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input. 样例 #1 样例输入 #1 8 babababa样例输出 #1 24思路 根据 border 与周期的关系我们知道我们要求的就是每个前缀的最小 border。 对于S[1 : i] 如果其最小的 border j满足 i − j ≥ i 2 i-j\geq \frac{i}{2} i−j≥2i​ 就可以为答案累计 。 根据迭代 next 遍历 border 集合的原理我们可以对每个前缀s[1 : i]维护一个 m n i mn_i mni​表示由i不断跳 next 所能得到的最小的非 0 border。 容易发现如果 n e x t i 0 next_i0 nexti​0那么 m n i i mn_ii mni​i 否则 m n i m n n e x t i mn_imn_{next_i} mni​mnnexti​​ 。 另外如果把本题放到 border 树上可以发现这个要求的东西就是每个节点属于根节点长度为 0 的前缀的哪个子树。 AC代码 #includebits/stdc.h using namespace std; const int N1000010; long long n,i,j; char s[N]; long long ne[N],ans; int main(){scanf(%d%s,n,s1);for(i2,j0;in;i){while(js[i]!s[j1])jne[j];if(s[i]s[j1])j;ne[i]j;}for(i2,j2;in;i,ji){while(ne[j])jne[j];if(ne[i])ne[i]j;ansi-j;}coutansendl; } [BOI2009] Radio Transmission 无线传输 题目描述 给你一个字符串 s 1 s_1 s1​它是由某个字符串 s 2 s_2 s2​ 不断自我连接形成的保证至少重复 2 2 2 次。但是字符串 s 2 s_2 s2​ 是不确定的现在只想知道它的最短长度是多少。 输入格式 第一行一个整数 L L L表示给出字符串的长度。 第二行给出字符串 s 1 s_1 s1​ 的一个子串全由小写字母组成。 输出格式 仅一行表示 s 2 s_2 s2​ 的最短长度。 样例 #1 样例输入 #1 8 cabcabca样例输出 #1 3提示 样例输入输出 1 解释 对于样例我们可以利用 abc \texttt{abc} abc 不断自我连接得到 abcabcabcabc \texttt{abcabcabcabc} abcabcabcabc读入的 cabcabca \texttt{cabcabca} cabcabca是它的子串。 规模与约定 对于全部的测试点保证 1 L ≤ 1 0 6 1 L \le 10^6 1L≤106。 思路 本题考查的是对next数组的理解其实答案就是n-ne[n] AC代码 #includebits/stdc.h using namespace std; const int N1000010; int n,m,i,j; char p[N],s[N]; int ne[N]; int main(){scanf(%d%s,n,p1);for(i2,j0;in;i){while(jp[i]!p[j1])jne[j];if(p[i]p[j1])j;ne[i]j;}printf(%d\n,n-ne[n]); } [COCI2011-2012#4] KRIPTOGRAM 题目描述 现有一段明文和一部分密文。明文和密文都由英文单词组成且密文中的一个单词必然对应着明文中的一个单词。 求给出的密文在明文中可能出现的最早位置。 输入格式 第一行若干个英文单词和一个 \)\texttt $\(表示明文。 第二行若干个英文单词和一个 \)\texttt $\(表示密文。 每行末尾的 \)\texttt $\( 用于表示该行结束。数据保证没有多个 \)\texttt $\( 出现在同一行的情况。 输出格式 输出密文在明文中可能出现的最早位置即密文的第一个单词在明文中可能出现的最早位置。 样例 #1 样例输入 #1 a a a b c d a b c \) x y \(样例输出 #1 3样例 #2 样例输入 #2 xyz abc abc xyz \) abc abc \(样例输出 #2 2样例 #3 样例输入 #3 a b c x c z z a b c \) prvi dr prvi tr tr x \(样例输出 #3 3提示 【数据规模与约定】 对于 100 % 100\% 100% 的数据明文和密文所对应字符串的长度不超过 1 0 6 10^6 106输入的单词均由小写字母组成。 【提示与说明】 题目译自 COCI 2011-2012 CONTEST #4 Task 6 KRIPTOGRAM。 本题分值按 COCI 原题设置满分 140 140 140。 思路 在传统的 KMP 算法中我们直接比较字符之间是否相等。 针对此题的情况只需要把判断式换成i - preA[i] j - preB[j] || ! preB[j] preA[i] i - j就行 AC代码 #include bits/stdc.h using namespace std; const int N 1e6 10; string a[N], b[N]; int lena, lenb; int sp_len[N], prea[N], preb[N]; void getPre(string str[], int pre[], int length) {unordered_mapstring, int last_pos;for (int i1;ilength;i) {pre[i]last_pos[str[i]];last_pos[str[i]]i;} } void getSpLen() {int i2,j1;while (ilenb) {if(i-preb[i]j-preb[j]||!preb[j]preb[i]i-j)sp_len[i]j;else if(j1)jsp_len[j-1]1;else i;} } int main() {string x;while (cinx,x!\))a[lena]x;while (cinx,x!$)b[lenb]x;getPre(a,prea,lena);getPre(b,preb,lenb);getSpLen();int i1,j1;while (ilena) {if(i-prea[i]j-preb[j]||!preb[j]prea[i]i-j)i, j;else if(j1)jsp_len[j-1]1;else i;if(jlenb){couti-lenbendl;return 0;}}cout-1endl;return 0; }这是我的第十九篇文章如有纰漏也请各位大佬指正 辛苦创作不易还望看官点赞收藏打赏后续还会更新新的内容。