思路
广义SAM的题目，先全部插入，然后每个字符串在SAM上匹配，如果发现当前sz小于k（就是前缀不满足条件），就跳fail（找前缀的后缀，就是找子串）到满足条件为止，然后一个满足条件的节点，它的所有parent Tree上的祖先也必定满足条件，所以一个满足条件的节点的贡献就是它的maxlen
ps:貌似求sz除了我这种，还可以set启发式合并
代码
#include#include #include #include #include #include using namespace std;int maxlen[201000],minlen[201000],trans[201000][26],suflink[201000],ans[201000],sz[201000],last[201000],endpos[201000],Nodecnt,n;string s[101000];int New_state(int _maxlen,int _minlen,int *_trans,int _sz,int _last,int _suflink){ ++Nodecnt; maxlen[Nodecnt]=_maxlen; minlen[Nodecnt]=_minlen; if(_trans) for(int i=0;i<26;i++) trans[Nodecnt][i]=_trans[i]; sz[Nodecnt]=_sz; last[Nodecnt]=_last; suflink[Nodecnt]=_suflink; return Nodecnt; }void update(int u,int x){ while(u&&last[u]!=x){ last[u]=x; sz[u]++; u=suflink[u]; }}int add_len(int u,int c,int inq){ if(trans[u][c]){ int v=trans[u][c]; if(maxlen[v]==maxlen[u]+1){ update(v,inq); endpos[v]++; return v; } int y=New_state(maxlen[u]+1,0,trans[v],sz[v],last[v],suflink[v]); suflink[v]=y; minlen[v]=maxlen[y]+1; while(u&&trans[u][c]==v){ trans[u][c]=y; u=suflink[u]; } minlen[y]=maxlen[suflink[y]]+1; update(y,inq); return y; } else{ int z=New_state(maxlen[u]+1,0,NULL,0,0,0); endpos[z]=1; while(u&&trans[u][c]==0){ trans[u][c]=z; u=suflink[u]; } if(!u){ suflink[z]=1; minlen[z]=1; update(z,inq); return z; } int v=trans[u][c]; if(maxlen[v]==maxlen[u]+1){ suflink[z]=v; minlen[z]=maxlen[v]+1; update(z,inq); return z; } int y=New_state(maxlen[u]+1,0,trans[v],sz[v],last[v],suflink[v]); suflink[v]=suflink[z]=y; minlen[v]=minlen[z]=maxlen[y]+1; while(u&&(trans[u][c]==v)){ trans[u][c]=y; u=suflink[u]; } minlen[y]=maxlen[suflink[y]]+1; update(z,inq); return z; }}int k,in[200100];queue q;int main(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); Nodecnt=1; scanf("%d %d",&n,&k); for(int i=1;i<=n;i++){ // scanf("%s",s+1); cin>>s[i]; int last=1,len=s[i].length(); // cout< <