SAM建立模板

int extend(int x,int p) {
    int np=++tot;sam[np].len=sam[p].len+1;
    while (p&&!sam[p].son[x]) sam[p].son[x]=np,p=sam[p].pr;
    if (!p) sam[np].pr=1;else {
        int q=sam[p].son[x];
        if (sam[q].len==sam[p].len+1) sam[np].pr=q;
        else {
            int nq=++tot;
            sam[nq]=sam[q];
            sam[nq].len=sam[p].len+1;
            sam[q].pr=sam[np].pr=nq;
            while (p&&sam[p].son[x]==q) sam[p].son[x]=nq,p=sam[p].pr;
        }
    }
    return np;
}