php毕业设计代做网站,个人域名用来做淘宝客网站,装修公司展厅工艺样板,临猗商城网站建设平台首先#xff0c;我们来定义一下淋漓尽致子串。 1.令原串为S。2.设子串的长度为len#xff0c;在原串S中出现的次数为k#xff0c;令其出现的位置为p1#xff0c; p2#xff0c; ....pk(即这个子串在原串中[pi#xff0c;pi len - 1]中出现)。 3.若k1#xff0c;则该子串… 首先我们来定义一下淋漓尽致子串。 1.令原串为S。 2.设子串的长度为len在原串S中出现的次数为k令其出现的位置为p1 p2 ....pk(即这个子串在原串中[pipi len - 1]中出现)。 3.若k1则该子串不是淋漓尽致子串。 4.若存在pipj(i ! j)使得S[pi - 1] S[pj - 1]则该子串不是淋漓尽致子串。 5.若存在pipj(i ! j)使得S[pi len] S[pj len]则该字串不是淋漓尽致字串。 否则该子串为淋漓尽致子串。 我想知道这个串有多少个本质不同的淋漓尽致子串。 数据范围 |S| 100000 S由小写字母组成。 考虑用SAM来分析一下题目中的条件 首先出现超过一次即sz[i]1 条件4即满足在parent树上没有一个i的儿子j满足sz[j]1 条件5满足在转移DAG上没有一个儿子j满足sz[j]1 于是每找到一个节点就会为答案贡献1 #pragma GCC opitmize(O3)
#pragma G opitmize(O3)
#includestdio.h
#includestring.h
#includealgorithm
#define N 200010
using namespace std;
char str[N]; int ans0;
int s[N][26],mx[N],sz[N],f[N];
int n,m,cnt1,lst1,v[N],r[N];
inline int extend(int c){int plst,nplstcnt,q,nq;mx[np]mx[p]1; sz[np]1;for(;!s[p][c];pf[p]) s[p][c]np;if(!p) return f[np]1;qs[p][c];if(mx[q]mx[p]1) f[np]q;else{nqcnt;mx[nq]mx[p]1;f[nq]f[q]; f[q]f[np]nq;memcpy(s[nq],s[q],262);for(;ps[p][c]q;pf[p]) s[p][c]nq;}
}
int main(){scanf(%s,str1); nstrlen(str1);for(int i1;in;i) extend(str[i]-a);for(int i1;icnt;i) v[mx[i]];for(int i1;in;i) v[i]v[i-1];for(int icnt;i;--i) r[v[mx[i]]--]i;for(int icnt;i;--i) sz[f[r[i]]]sz[r[i]];memset(v,*sz0,sizeof v);for(int p,icnt;i;--i){pr[i];if(sz[p]1) v[f[p]]1;if(sz[p]1) v[p]1; else for(int c0;c26;c)if(sz[s[p][c]]1){ v[p]1; break; }}for(int icnt;i;--i) ans!v[i];printf(%d\n,ans);
} 转载于:https://www.cnblogs.com/Extended-Ash/p/9477134.html
