给自己的家乡建设网站,wordpress底部友情链接,临漳+网站建设,学校英文版网站建设后缀自动机#xff0c;处理所有子串。 注意#xff1a;nq节点的建立#xff0c;是因为新加了一个字母使原本为一个状态的东西必须分为两个状态#xff0c;例如ba到baa#xff0c;a的出现次数变多#xff0c;a状态与ba状态分离。baa的新pnt不能是ba#xff0c;因为空节点…后缀自动机处理所有子串。 注意nq节点的建立是因为新加了一个字母使原本为一个状态的东西必须分为两个状态例如ba到baaa的出现次数变多a状态与ba状态分离。baa的新pnt不能是ba因为空节点可以通过两种方式到达ba状态它的pnt的状态就不唯一了。换句话说不能由截断前缀得到不符合的节点的后缀与儿子相同则跳指针时会出现问题。所以建立节点把是节点的状态分离出来让的。因为节点比节点短所以的的。 每个节点的转移他们的都应该具备 题目大意 给定一个字符串求每个长度的子串出现次数的最大值 tyvj 4123用pnt树size从大往小更新用并查集维护是否更新过 模板代码 #includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
#define maxn 200020struct node{int next[26],val;int pnt;
}sam[maxn * 2];
struct node2{int sz,num;bool operator (const node2 a) const{return sz a.sz; }
}data[maxn * 2];
char a[maxn];
int n,tot,last,root;
int fa[maxn];
int num[maxn],ans[maxn],b[maxn];inline void add(int x){int np tot,p last;sam[np].val sam[p].val 1;data[np].sz 1;while ( !sam[p].next[x] p ) sam[p].next[x] np, p sam[p].pnt;int q sam[p].next[x];if ( !q ) sam[np].pnt root,sam[root].next[x] np;else if ( q sam[p].val 1 sam[q].val ) sam[np].pnt q;else{int nq tot;sam[nq].val sam[p].val 1;sam[nq].pnt sam[q].pnt;sam[np].pnt sam[q].pnt nq;memcpy(sam[nq].next,sam[q].next,sizeof(sam[q].next));while ( p sam[p].next[x] q ) sam[p].next[x] nq , p sam[p].pnt;if ( sam[p].next[x] q ) sam[p].next[x] nq; //特判p跳到根后的情况}last np;
}
inline void getsize(){for (int i 0 ; i tot ; i) num[sam[i].val];for (int i 1 ; i n ; i) num[i] num[i - 1]; //从小到大for (int i tot ; i 0 ; i--) b[--num[sam[i].val]] i;for (int i tot ; i 0 ; i--) if ( sam[b[i]].pnt ! b[i] ) data[sam[b[i]].pnt].sz data[b[i]].sz;
}
inline int getfa(int x){if ( x fa[x] ) return x;return fa[x] getfa(fa[x]);
}
int main(){scanf(%s,a 1);n (int) strlen(a 1);for (int i 1 ; i n ; i) add(a[i] - a);getsize();for (int i 1 ; i n 2 ; i) fa[i] i;for (int i 1 ; i tot ; i) data[i].num i;sort(data 1,data tot 1);for (int i 1 ; i tot ; i){int x data[i].num;for (int j getfa(sam[sam[x].pnt].val 1) ; j sam[x].val ; j getfa(j 1)){ans[j] max(data[i].sz,ans[j]);fa[j] fa[j 1];}}for (int i 1 ; i n ; i) printf(%d\n,ans[i]);return 0;
}转载于:https://www.cnblogs.com/zqq123/p/5201312.html
