RT,写的SAM,干了半天永远最后一个点MLE,是我写假了还是这玩意就是针对指针= =
// Author: Ame__
#include<bits/stdc++.h>
#define _ 0
#define qwq double
#define AME__DEBUG
#define LL long long
#define bomb exit(0)
#define LOG(FMT...) fprintf(stderr , FMT)
#define TOWA(FMT...) fprintf(stdout , FMT)
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
char buf_s; while(buf_s != '-' && !isdigit(buf_s)) buf_s = getchar();
bool register _nega_ = false; if(buf_s == '-'){ _nega_ = true; buf_s = getchar(); }
_x_ = 0; while(isdigit(buf_s)){ _x_ = _x_ * 10 + buf_s - '0'; buf_s = getchar(); } if(_nega_) _x_ = -_x_;
}
const int kato = 1e6 + 10;
const int atri = 2e6;
template <typename _n_> bool cmax(_n_ &a , const _n_ &b){ return a < b ? a = b , 1 : 0; }
template <typename _n_> bool cmin(_n_ &a , const _n_ &b){ return a > b ? a = b , 1 : 0; }
int n , c[atri];
char s[200][kato] , t[kato];
namespace towa{
struct SuffixAutoMaton{
protected:
struct node{
static const size_t CHARSET_SIZE = 27;
node *ch[CHARSET_SIZE] , *nxt;
int len , size;
node(node *nxt = 0x0 , int len = 0 , int size = 0): nxt(nxt) , len(len) , size(size){
memset(ch , 0x0 , sizeof ch);
}
}*root , *ls , *tail , *id[atri] , _pool[atri];
inline void extend(int c){
node *u = new(tail ++) node(0x0 , ls -> len + 1 , 1) , *v = ls;
for(; v && !v -> ch[c] ; v = v -> nxt) v -> ch[c] = u;
if(!v) u -> nxt = root;
else if(v -> ch[c] -> len == v -> len + 1) u -> nxt = v -> ch[c];
else{
node *n = new(tail ++) node(0x0 , v -> len + 1) , *o = v -> ch[c];
copy(o -> ch , o -> ch + node::CHARSET_SIZE , n -> ch);
n -> nxt = o -> nxt , o -> nxt = u -> nxt = n;
for(; v && v -> ch[c] == o ; v = v -> nxt) v -> ch[c] = n;
}
ls = u;
}
void clear(){ tail = _pool; root = ls = new(tail ++) node(); }
public:
SuffixAutoMaton(){ clear(); }
inline void insert(char *s){ for(char *p = s ; *p ; p ++) extend(*p - 'a'); }
inline void get_size(){
int maxlen = 0;
for(node *o = _pool ; o != tail ; o ++) c[o -> len] ++ , maxlen = max(maxlen , o -> len);
for(int i = 1;i <= maxlen;i ++) c[i] = c[i] + c[i - 1];
for(node *o = _pool ; o != tail ; o ++) id[--c[o -> len]] = o;
for(int i = tail - _pool - 1 ; i ; i --){
node *o = id[i];
if(o -> nxt) o -> nxt -> size += o -> size;
}
}
inline int get_ans(char *s){
node *o = root;
for(char *p = s ; *p ; p ++) o = o -> ch[*p - 'a'];
return o -> size;
}
}yuni;
}
inline int Ame_(){
#ifdef AME__
freopen(".in" , "r" , stdin); freopen(".out" , "w" , stdout); int nol_cl = clock();
#endif
mian(n); char *q = t;
for(int i = 0;i < n;i ++){
scanf("%s" , s[i]);
for(char *p = s[i] ; *p ; p ++) *q ++ = *p;
*q ++ = 'z' + 1;
}
towa::yuni.insert(t); towa::yuni.get_size();
for(int i = 0;i < n;i ++) TOWA("%d\n" , towa::yuni.get_ans(s[i]));
#ifdef AME__TIME
LOG("Time: %dms\n", int((clock() - nol_cl) / (qwq)CLOCKS_PER_SEC * 1000));
#endif
return ~~(0^_^0); /*さようならプログラム*/
}
int Ame__ = Ame_();
int main(){;}