个人博客 题目链接 题意： 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等 题解： 裸的马拉车（Manacher）算法，直接上板子就够了。如果你没有马拉车板子，或者说你不会马拉车，请见Manacher最长回文串算法 代码： #include<stdio.h> #include<algorithm> #include<cstring> #define met(a) memset(a,0,sizeof(a)); using namespace std; t...

个人博客 题目链接 题意： 有n个环形字符串，一个环形字符串移动会形成不能的字符串，我们把它们看作同一串字符串，求有多少个不同的字符串 题解： 用最小表示法把每个串的最小字典序找出来, <mark>(如果两个循环串相等则他们的最小字典序也一定相等)</mark>,set带有除重功能，因为set具有除重功能所以用set来存每个串求出的最小字典序 代码： #include<stdio.h> #include<bits/stdc++.h> using namespace std; typedef long long ll; const...

个人博客 题目链接 题意： 中文题面，题意也说得非常清楚了，给一个文本串，求文本串中有多少个不重复的模式串 题解： kmp标准做法，甚至基本没有变动。 判断的时候，每当完整的匹配一次之后令j=0，ans++，即模式串的下标从0开始，匹配数量加1 代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<cstdlib&g...

个人博客 题目链接 题意： 给你两个数组的所有元素，让你对它们进行匹配，当位置为多少时候它们能完全匹配。 题解： 直接跑KMP就可以了，唯一注意的…emmm…应该不用注意吧，也就原先是字符串，现在把字符串换成数组超级大水题 代码： #include<stdio.h> #include<bits/stdc++.h> using namespace std; int s[1000100],t[11000]; int nex[1000100];//nex数组大小和短串一致 int ans,n,m; inline void get_nex() { i...

个人博客 题目链接 题意： 给出两个串，用这两个串组成一个新串，使新串包含这两个串，问这个新串的长度最小是多少； 题解： 显然，对于两个串A，B；A如果是B的子串或者B如果是A的子串的话，直接输出那个母串的长度即可，如果没有这种关系，那么看一个串的后缀是否是另一个串的前缀，如果某个串的后缀与另一个串的前缀的公共部分最长，则答案=A.length+B.length-公共长度，所以可以直接用kmp去做。(kmp匹配最后j值为模式串前缀和主串后缀最长公共长度) 代码： #include<stdio.h> #include<algorithm> #includ...

基本语法 1.注释---------# 标注文本 2.数字 整数，不区分long和int 进制0xa (16进制的10),0o10（8进制的10）,0b10（2进制的10） bool，2个值True，False 浮点数 1.2，3.1415.-0.12，1.46e9等价于1.46*10^9 复数，1+2j 3.字符串 使用‘ “单双引号引用字符的序列 ‘ ’ ‘ ” “ ” 单双三引号，可以跨行，可以在其中自由的使用单双引号 print(''' welcome 'to' python''')...

博主CSDN 题目链接 题意： 给定一个字符串S，求至少出现k次的最长重复子串，这k个子串可以重叠。 题解： 后缀数组。先二分答案，然后将后缀分成若干组。这里要判断的是有没有一个组的后缀个数不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。。 代码： /* 题意：找出出现k次的可重叠的最长子串的长度 这都是套路题了，二分长度L,按照height值分组，在同一组内的组数如果大于K,则成立。 */ #include <cstdio> #include <cstring> #include <al...

CSDN 题目链接 题意： 给你一个字符串，你可以将该字符串的任意长度后缀截取下来然后接到最前面，让你统计所有新串中有多少种字典序小于、等于、大于原串。 题解： 首先我们将原串扩展成两倍，算一遍扩展KMP（自匹配），时间复杂度O(n)。这样一来，我们就得到了eKMP[i]，eKMP[i]代表s[i…len-1]与s的最长公共子串。为了避免重复子串重复计数，我们先求出s的最小循环节：然后我们只需统计最小循环节以内的字符就可。当eKMP[i]>=len时，显然是原串，E++;否则我们只需比较一位就可判断大小，即：比较s[i+eKMP[i]]和s[eKMP[i]]的大小。为什么只...

#include<stdio.h> #include<bits/stdc++.h> using namespace std; int n,p,a,b,m,x,y,ans; struct node { int l,r,w,f; }tree[400001]; inline void build(int k,int ll,int rr) {//建树 tree[k].l=ll,tree[k].r=rr; if(tree[k].l==tree[k].r){ scanf("%d",&tree[k].w); ...

博主博客链接 1.Node及Hexo安装 hexo是什么？简单的说，就是一个静态博客的生成工具也可以说是一个搭建静态博客的框架，我这个博客就是就是基于hexo生成的。9月份把这个博客用hexo折腾出来，前几天ACM区域赛事结束了，所以想记录下来折腾的过程，留着以后备用。这里只说如何在windows下成功安装hexo并运行起来，关于主题以及配置不做记录。 安装Node.js 因为Hexo是基于Node.js的，所以必须先安装Node，所以请点击这里去下载适合自己windows版本的Node吧。 （注意：在安装步骤里Custom Setup这一步记得选Add to PATH）。 安装好...

HDU - 3374 - String Problem 个人博客 题意： 给你一个字符串，问这个字符串经过移动后的字典序最小的字符串的首字符位置和字典序最大的字符串的首字符的位置，和能出现多少次最小字典序的字符串和最大字典序的字符串 题解： 利用最小表示法与最大表示法O(n)复杂度求出最小字典序和最大字典序串出现位置，然后利用kmp求出next，利用next数组性质求出循环节次数，因为最小和最大字典序串出现次数等于循环节次数（这个关系可以脑补下） 代码： #include<stdio.h> #include<bits/stdc++.h> using n...

最小表示法伪代码： 最小表示法的算法思路是维护两个指针i,j。 令i=0,j=1 如果S[i] > S[j] i=j, j=i+1 如果S[i] < S[j] j++ 如果S[i]==S[j] 设指针k，分别从i和j位置向下比较，直到S[i] != S[j] 如果S[i+k] > S[j+k] i=i+k 否则j++ 返回i和j的小者 模版： #include<stdio.h> #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6...

博主链接 题目链接 题意： 给一个n，求出对应m满足（1+sqrt(2))^n==sqrt(m)+sqrt(m-1) 题解： 可以将（1+sqrt(2))^n一项项拆开后发现 sqrt(1)+sqrt(2) sqrt(9)+sqrt(8) sqrt(49)+sqrt(50) sqrt(492+9)+sqrt(492+10) 发现如果n为奇数f(n)=f(n-2)+2f(n-1)+1; 为偶数时f(n)=f(n-2)+2f(n-1); 所以可以推出状态转移矩阵 2 1 1 0 #include<stdio.h> #include<bits/stdc++.h&gt...

博主链接 题目链接 题意： 给出A数组，共有N个数，你可以选其中一些出来XOR（至少一个数）. 所以可能的XOR结果值排序后去重，问你排在第k个的结果值是多少. 题解： 线性基有个性质：线性基内任意集合异或结果唯一，而所有数异或0还是本身 所以每个数字出现的个数就等于(1*异或值为0的集合个数) = 2^(n-cnt) 所以问题就转化为求线性基有效位cnt，和q在所有异或值中第几大 #include<stdio.h> #include<bits/stdc++.h> using namespace std; typedef long long int ll...