题意:有n个串,询问每个串有多少子串在n个串中出现了至少k次.

题解:sam,每个节点开一个set维护该节点的字符串有哪几个串,启发式合并set,然后在sam上走一遍该串,对于每个可行的串,所有的fail都是可行的直接加上len,不可行就往fail上跳.

被for(int i=0;s[i];i++)给骚死了,一直tle....

//#pragma GCC optimize(2)//#pragma GCC optimize(3)//#pragma GCC optimize(4)//#pragma GCC optimize("unroll-loops")//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include
    
     #define fi first#define se second#define db double#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector
     
      #define mod 1000000007#define ld long double//#define C 0.5772156649//#define ls l,m,rt<<1//#define rs m+1,r,rt<<1|1#define pll pair
      
       #define pil pair
       
        #define pli pair
        
         #define pii pair
         
          #define ull unsigned long long//#define base 1000000000000000000#define fin freopen("a.txt","r",stdin)#define fout freopen("a.txt","w",stdout)#define fio ios::sync_with_stdio(false);cin.tie(0)inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}template
          
           inline T const& MAX(T const &a,T const &b){return a>b?a:b;}template
           
            inline T const& MIN(T const &a,T const &b){return a
            
             >=1;}return ans;}inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}using namespace std;const ull ba=233;const db eps=1e-5;const ll INF=0x3f3f3f3f3f3f3f3f;const int N=100000+10,maxn=1000000+10,inf=0x3f3f3f3f;int n,k;char s[N];vector
             
              v[N];struct SAM{ int last,cnt; int ch[N<<1][26],fa[N<<1],l[N<<1]; int sz[N<<1],id[N<<1]; set
              
               st[N<<1]; vi son[N<<1]; SAM(){cnt=1;} void ins(int c){ if(ch[last][c]) { int p=last,q=ch[last][c]; if(l[q]==l[p]+1)last=q; else { int nq=++cnt;l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof ch[q]); fa[nq]=fa[q];fa[q]=last=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } return ; } int p=last,np=++cnt;last=np;l[np]=l[p]+1; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; if(!p)fa[np]=1; else { int q=ch[p][c]; if(l[p]+1==l[q])fa[np]=q; else { int nq=++cnt;l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[nq]=fa[q];fa[q]=fa[np]=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } } void build(int id) { last=1;int len=strlen(s); for(int i=0;i