看一次忘一次，蛋疼死了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <cstdio>#include <cstring>#include <cstdlib>#include <cassert>const int char_size=26;const int pool_size=100000;class suffixs_automaton{public: struct suffix_node{ bool start; int length; suffix_node * clean(){ return this; } suffix_node*ch[char_size]; suffix_node*f; suffix_node(){ start=false; length=0; f=NULL;memset(ch,0,sizeof(ch)); }; };private: // 私有变量 suffix_node suffix_node_pool[pool_size+1]; int poolsize; suffix_node*alloca_node(){ if (poolsize==pool_size) {suffix_node *sn = new suffix_node();assert(sn);}return suffix_node_pool[poolsize++].clean();}; suffix_node*tail; suffix_node*start; int length;public: suffixs_automaton(int *c,int len); // [0,len) const suffix_node * get_start(); void add(int c);private: // 内部函数};suffixs_automaton::suffixs_automaton(int *c,int len){ poolsize = 0; start = tail = alloca_node(); start->start=true;length=0; for (int i=0;i<len;i++) add(c[i]);};const suffixs_automaton::suffix_node * suffixs_automaton::get_start(){ return start;};void suffixs_automaton::add(int c){ length++;suffix_node*p=tail;suffix_node*np=alloca_node(); np->length = tail->length+1; for (;!!p && !p->ch[c];p=p->f) p->ch[c]=np; tail = np; if (!p) {np->f=start;return ;} if (p->ch[c]->length==p->length+1) np->f=p->ch[c]; else { suffix_node*r = alloca_node();suffix_node *q=p->ch[c]; *r=*q; r->length = p->length+1; q->f=np->f=r; for (;p&&p->ch[c]==q;p=p->f) p->ch[c]=r; }};int p[]={0,2,0,3,3};suffixs_automaton SA(p,5);char c[255];void dfs(const suffixs_automaton::suffix_node *sn,int l){ assert(sn); if (l!=0) printf("%s\n",c); for (int i=0;i<5;i++) if (sn->ch[i]){ c[l]='A'+i; dfs(sn->ch[i],l+1); c[l]=0; }}int main(){ const suffixs_automaton::suffix_node *sn = SA.get_start(); dfs(sn,0); system("pause");}; |
2024年1月11日 04:13
For my part, a person like life-style? Systems work efficiently not waste time, since instance is made up of matter one’s life. how do i make google docs dark mode
2024年1月17日 07:59
Embrace opga's diverse paths, whether through soothing massages or romantic Kiss Room, and embark on a personal journey of self-discovery.