后缀数组，压状dp,最长回文子窜
字符窜同构的性质：同构字符窜拥有最小和最大的表示方法；
最长回文子窜：
1.首先暴力法：（n三方）
枚举每个起点和终点，然后单向扫描判断是不是回文子窜；
2.中心扩散法，（N方）
枚举每个中点，向外扩散，看以他为中心的回文子窜的长度是多少；
易证：复杂度N方
3.O(N)的做法；
我的理解：和扩展KMP有点相似，扩展KMP,我们为了不重复所以设定了破，po和ex[po]，然后我们讨论i可能的答案是否已经包含在扫描的里面了，如果包含了直接赋值，没包含继续扫描；
我们对中心扩散的方法进行改进，
1.思想： 1）将原字符串S的每个字符间都插入一个永远不会在S中出现的字符（本例中用“#”表示），在S的首尾也插入该字符，使得到的新字符串S_new长度为2*S.length()+1，保证Len的长度为奇数(下例中空格不表示字符，仅美观作用)；
例：S： a a b a b b a
S_new: # a # a # b # a # b # b # a #
2）根据S_new求出以每个字符为中心的最长回文子串的最右端字符距离该字符的距离，存入Len数组中，即S_new[i]—S_new[r]为S_new[i]的最长回文子串的右段（S_new[2i-r]—S_new[r]为以S_new[i]为中心的最长回文子串），Len[i] = r – i + 1;
S_new: # a # a # b # a # b # b # a #
Len: 1 2 3 2 1 4 1 4 1 2 5 2 1 2 1
Len数组性质：Len[i] – 1即为以Len[i]为中心的最长回文子串在S中的长度。在S_new中，以S_new[i]为中心的最长回文子串长度为2Len[i] – 1，由于在S_new中是在每个字符两侧都有新字符“#”，观察可知“#”的数量一定是比原字符多1的，即有Len[i]个，因此真实的回文子串长度为Len[i] – 1，最长回文子串长度为Math.max(Len) – 1。
3）Len数组求解（线性复杂度（O(n)））：
a.遍历S_new数组，i为当前遍历到的位置，即求解以S_new[i]为中心的最长回文子串的Len[i]; b.设置两个参数：sub_midd = Len.indexOf(Math.max(Len)表示在i之前所得到的Len数组中的最大值所在位置、sub_side = sub_midd + Len[sub_midd] – 1表示以sub_midd为中心的最长回文子串的最右端在S_new中的位置。起始sub_midd和sub_side设为0，从S_new中的第一个字母开始计算，每次计算后都需要更新sub_midd和sub_side；
c.当i < sub_side时，取i关于sub_midd的对称点j（j = 2sub_midd – i，由于i <= sub_side，因此2sub_midd – sub_side <= j <= sub_midd);当Len[j] < sub_side – i时，即以S_new[j]为中心的最长回文子串是在以S_new[sub_midd]为中心的最长回文子串的内部，再由于i、j关于sub_midd对称，可知Len[i] = Len[j]; 当Len[j] >= sub.side – i时说明以S_new[i]为中心的回文串可能延伸到sub_side之外，而大于sub_side的部分还没有进行匹配，所以要从sub_side+1位置开始进行匹配，直到匹配失败以后，从而更新sub_side和对应的sub_midd以及Len[i]；
d.当i > sub_side时，则说明以S_new[i]为中心的最长回文子串还没开始匹配寻找，因此需要一个一个进行匹配寻找，结束后更新sub_side和对应的sub_midd以及Len[i]。
我的理解：
实际上我们每次扫描得到了sub_mid和sub_side,利用回文串的对称性，我们来判断是否已经在答案里面了，不在的我们就继续扫描比较下去；
就是对中心扩散法的一种dp；
与那个啥z函数有点类似的想法，利用性质推到到已经求过的内容然后及进行求解，避免重复扫描；
Sting 的构造函数：
string str：生成空字符串
string s(str)：生成字符串为str的复制品
string s(str, strbegin,strlen)：将字符串str中从下标strbegin开始、长度为strlen的部分作为字符串初值
string s(cstr, char_len)：以C_string类型cstr的前char_len个字符串作为字符串s的初值
string s(num ,c)：生成num个c字符的字符串
string s(str, stridx)：将字符串str中从下标stridx开始到字符串结束的位置作为字符串初值
eg:
string str1; //生成空字符串
string str2(“123456789”); //生成”1234456789″的复制品
string str3(“12345″, 0, 3);//结果为”123”
string str4(“012345″, 5); //结果为”01234”
string str5(5, ‘1’); //结果为”11111″
string str6(str2, 2); //结果为”3456789″
大佬博客：https://www.cnblogs.com/jinkun113/p/4743694.html；
后缀数组：
复杂度：N(NlogN)
理论原理加模板：
后缀数组使用倍增法这里不加以叙述+桶排序；
先来了解一下桶排序，要拍一个1-99的数，我们先按照各位放到十个桶里，然后按照顺序取出来放到十位的桶里，这样我们在保证十位相同的时候个位小的先被放入桶里，所以答案的顺序就是对的，如图：
基于这个原理其实我们排序字符窜的时候也是先比较第一关键字是否相同然后判断第二关键字，所以我们在排序的时候，为了不多加一个桶，重复操作，我们可以按照第一关键字排序，然后按照第二关键字取出来，先被取出来的就是比较相同的一个排名区间里面比较小的，为什么是排名区间呢，我们桶排序时算出桶元素个数的前缀和，对于一个桶来说，他前面所拥有的元素都比他小，他后面桶的元素都比他大，所以我们知道的是一个区间，我们把元素小的先取出来附上排名，就可以确定这个区间的具体排名；
倍增：
我们发现有些没有第二关键字，，就当作是0，放在最前面，有些排名做了别人的第二和关键字，位子随着循环次数是2的k次方的关系；
接下来看我们在更新第一关键字的时候就是rk，我们要判断两个排名是否相同就是第一和第二关键字是否相同，然后重新附上排名；看代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN= ;
char s[MAXN];
int rk[MAXN],srk[MAXN],tax[MAXN],sa[MAXN],hi[MAXN];//rk第一关键字排名，srk第二关键字排名
int n,m=127;//’z’=126
void Rsort(int *rk,int *tp)
{
for(int i=1;i<=m;i++) tax[i]=0;//清空桶；
for(int i=1;i<=n;i++) tax[rk[i]]++;//按照第一关键字先放入不同的桶
for(int i=1;i<=m;i++) tax[i]+=tax[i-1];//要知道这个字符的排名就要先求出来他前面有多少个字符；
for(int i=1;i<=n;i++) sa[tax[rk[tp[i]]]–]=tp[i];//其实我们只要把桶中的每个元素取出来，他前面有多少数他的排名就是地基，只要按照第二个关键字把第一个关键字去出来
}
bool cmp(int r[],int a,int b,int k)
{
return r[a]==r[b]&&r[a+k]==r[b+k];
}
按照第一关键字放入不同的桶然后按照第二关键字把它取出来；完成基数排序；
void get_sa()
{
for(int i=1;i<=n;i++) rk[i]=a[i],tp[i]=i;
Rsort(rk,tp);
//因为我们要由2的k-1次到二的k次，那么需要找到下一个2的k-1次所在的位置的头位置，所以J代表我们要找的位置距离这个位置的距离
for(int j=1;j<n;j<<=1,m=p)//m=p的意思是我们看看这个排名最大到p所以只需要P个桶来排序
{
int p=0;
// 没有第二关键字，可以作为最小的0来处理
for(int i=1;i<=j;i++) srk[++p]=n-j+1;
// 然后我么根据平移的关系通过sa[i]遍历所有后缀的是否在可以作为其他字符的第二关键字
for(int i=1;i<=n;i++) if(sa[i]>j) srk[++p]=sa[i]-j;
Rsort(rk,srk);//按照第一关键字放入桶，按照第二关键字取出来
swap(rk,srk);//我们要更新rk，先把他放到第二关键字排序里面，因为如果第一关键字和第二关键字相同，则这两个字符窜相同
rk[sa[1]]=p=1;
for(int i=2;i<=n;i++)
rk[sa[i]]=comp(srk,sa[i],sa[i-1],j)?p:++p;//判断两个字符窜是否具有相同的排序
}
}
void gethi()
{
for (rint i=1;i<=n;++i) rk[sa[i]]=i;//使它没有重复排名
for(int i=1,j=0;i<=n;i++)
{
if(rk[i]==1) continue;//第一名的height=0
if(j) j–;
while(s[i+j]==s[sa[rk[i]-1]+j]) j++;
hi[rk[i]]=j;
}
}
int main()
{
scanf(“%s”,s+1);
n=strlen(s+1)； 从第一个位置开始输入
get_sa();
}
“`
作用用来O(N)求
最长公共前缀：LCA；
我们先看LCA的两条性质：
关于LCP的几条性质
显而易见的
- LCP(i,j)=LCP(j,i);
- LCP(i,i)=len(sa[i])=n-sa[i]+1;
这两条性质有什么用呢？对于i>j的情况，我们可以把它转化成i<j，对于i==j的情况，我们可以直接算长度，所以我们直接讨论i<j的情况就可以了。
我们每次依次比较字符肯定是不行的，单次复杂度为O(n)，太高了，所以我们要做一定的预处理才行。
LCP Lemma
LCP(i,k)=min(LCP(i,j),LCP(j,k)) 对于任意1<=i<=j<=k<=n
证明：设p=min{LCP(i,j),LCP(j,k)}，则有LCP(i,j)≥p,LCP(j,k)≥p。
设suff(sa[i])=u,suff(sa[j])=v,suff(sa[k])=w;
所以u和v的前p个字符相等，v和w的前p个字符相等
所以u和w的前p的字符相等，LCP(i,k)>=p
设LCP(i,k)=q>p 那么q>=p+1
因为p=min{LCP(i,j),LCP(j,k)}，所以u[p+1]!=v[p+1] 或者 v[p+1]!=w[p+1]
但是u[p+1]=w[p+1] 这不就自相矛盾了吗
所以LCP(i,k)<=p
综上所述LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}
LCP Theorem
LCP(i,k)=min(LCP(j,j-1)) 对于任意1<i<=j<=k<=n
这个结合LCP Lemma就很好理解了
我们可以把i~k拆成两部分i~(i+1)以及(i+1)~k
那么LCP(i,k)=min(LCP(i,i+1),LCP(i+1,k))
我们可以把(i+1)~k再拆，这样就像一个DP，正确性显然
怎么求LCP？
我们设height[i]为LCP(i,i-1)，1<i<=n，显然height[1]=0;
由LCP Theorem可得，LCP(i,k)=min(height[j]) i+1<=j<=k
这里的i，j是sa中的顺序；这个很容易证明；把换元到sa数组
那么height怎么求，枚举吗？NONONO，我们要利用这些后缀之间的联系
设h[i]=height[rk[i]]，同样的，height[i]=h[sa[i]];
那么现在来证明最关键的一条定理：
h[i]>=h[i-1]-1;
这个证明我觉得看上面第一个大佬的博客吧，我对代码进行一下简单的说明
证明过程来自曲神学长的blog，我做了一点改动方便初学者理解：
首先我们不妨设第i-1个字符串按排名来的前面的那个字符串是第k个字符串，注意k不一定是i-2，因为第k个字符串是按字典序排名来的i-1前面那个，并不是指在原字符串中位置在i-1前面的那个第i-2个字符串。
这时，依据height[]的定义，第k个字符串和第i-1个字符串的公共前缀自然是height[rk[i-1]]，现在先讨论一下第k+1个字符串和第i个字符串的关系。
第一种情况，第k个字符串和第i-1个字符串的首字符不同，那么第k+1个字符串的排名既可能在i的前面，也可能在i的后面，但没有关系，因为height[rk[i-1]]就是0了呀，那么无论height[rk[i]]是多少都会有height[rk[i]]>=height[rk[i-1]]-1，也就是h[i]>=h[i-1]-1。
第二种情况，第k个字符串和第i-1个字符串的首字符相同，那么由于第k+1个字符串就是第k个字符串去掉首字符得到的，第i个字符串也是第i-1个字符串去掉首字符得到的，那么显然第k+1个字符串要排在第i个字符串前面。同时，第k个字符串和第i-1个字符串的最长公共前缀是height[rk[i-1]]，
那么自然第k+1个字符串和第i个字符串的最长公共前缀就是height[rk[i-1]]-1。
到此为止，第二种情况的证明还没有完，我们可以试想一下，对于比第i个字符串的排名更靠前的那些字符串，谁和第i个字符串的相似度最高（这里说的相似度是指最长公共前缀的长度）？显然是排名紧邻第i个字符串的那个字符串了呀，即sa[rank[i]-1]。但是我们前面求得，有一个排在i前面的字符串k+1，LCP(rk[i],rk[k+1])=height[rk[i-1]]-1;
又因为height[rk[i]]=LCP(i,i-1)>=LCP(i,k+1)
所以height[rk[i]]>=height[rk[i-1]]-1，也即h[i]>=h[i-1]-1。
void gethi()
{
for (rint i=1;i<=n;++i) rk[sa[i]]=i;//使它没有重复排名
for(int i=1,j=0;i<=n;i++)
{
if(rk[i]==1) continue;//第一名的height=0
if(j) j–;//j只要减1，然后继续去匹配
while(s[i+j]==s[sa[rk[i]-1]+j]) j++;//这一部就是求第i个字符窜在sa中和他前面一个匹配；
hi[rk[i]]=j;
}
}
Next 数组
根本目的：我们在匹配时为了不重复扫描就要看已经扫描的多少能被再次利用，在性质上的体现就是已经扫描的一段的后缀等于他的前缀；
算法的复杂度是O（N）;
算法实现：思想我们利用上一个字母的前缀和后缀的基础上加上新的一个元素，可以下行不行，如果不行，我们缩短可匹配的数列k=next[k];
算法优化，因为我们每次失配都会利用next跳到要匹配的点去，但是如果这个点和已知点一直相同，导致查询的复杂度变大，我们在next数组赋值的时候，那么加一部判断，看一下这两个点是否线段，nxt()=nxt();
性质可以用来字符窜匹配第一次匹配的位置，或者是能匹配几次，或者要匹配的字符窜在原文中的而次数，我们也可以用来求字符窜的最小循环节的长度。
性质：每一个nxt都对应着一个也是唯一一个与该字符串没有重合的前缀，我们可以我们可以通过这个性质来确定所有前缀出现的次数，关系是nxt[j]-(重合部分/2/j前面循环节的长度向上取整)*len，
性质二，对于最后一个nxt我们可以知道那些后缀直接完全与原来的字符窜匹配；
动态规划：
又名是记忆搜素规划；
因为我们操作一步以后变成变成相同的最优化低纬度问题，特点是，每一个状态的值固定，而且状态能往最基本的状态转移。与递归相似，但是记忆化搜素可以大规模优化时间复杂度；
就像背包问题，我们一般问剩下的空间最多能装多少东西，而区间的动态规划，就是我们发现一个空间能够变成下一个小问题。
状压dp:
复杂度很高；
- 适合解决小规模情况而且复杂的题目；一般数据范围在时几；
- 适合解决每个小东西状态只有两种的情况，我们用0，1每个bit的0，1，表示两种状态，而一个数代表着一种状态；
- 我们一般考虑两个状态之间的关系，所以要枚举0到（1<<m）-1的所有情况，看看当前状态是否由其他状态得到，或者可以转移到其他状态；
- 同时压状dp要具有无后效性就是，该行对下面一行有影响，或者对下面多行有影响但是很好表示；
- 压状dp分为两大种（我至今只见到了两大种），一个是dfs的压状，我们通过上一个状态知道下一个状态那些路不可以走，那些可以走，典型题，还是八皇后，还有一种是直接一个数代表一个完整的状态，看看他的最优解；
压状dp常用的运算要熟
- &判断每个位置的状态，“|”两个状态叠加，“~”取凡，找出可行的状态；lowbit()，逐一取出可行的状态；<<判断某个状态；
状压dp一般分为找枚举所有状态找其中的合法状态，然后这个合法状态能转移到其他什么状态；
Views: 171
欧拉通路/欧拉回路
2条评论
admin
请善用提供的功能，代码做代码块，列表用列表，适当缩进
admin
网页链接可以插入链接