| 23 | } |
| 24 | |
| 25 | void extend(char c){ |
| 26 | int cur = sz++; |
| 27 | node[cur].cnt = 1; |
| 28 | node[cur].len = node[last].len + 1; |
| 29 | int p = last; |
| 30 | while(p != -1 && !node[p].nxt.count(c)){ |
| 31 | node[p].nxt[c] = cur; |
| 32 | p = node[p].link; |
| 33 | } |
| 34 | if(p == -1){ |
| 35 | node[cur].link = 0; |
| 36 | } else { |
| 37 | int q = node[p].nxt[c]; |
| 38 | if(node[p].len + 1 == node[q].len){ |
| 39 | node[cur].link = q; |
| 40 | } else { |
| 41 | int clone = sz++; |
| 42 | node[clone].len = node[p].len + 1; |
| 43 | node[clone].nxt = node[q].nxt; |
| 44 | node[clone].link = node[q].link; |
| 45 | while(p != -1 && node[p].nxt[c] == q){ |
| 46 | node[p].nxt[c] = clone; |
| 47 | p = node[p].link; |
| 48 | } |
| 49 | node[q].link = node[cur].link = clone; |
| 50 | } |
| 51 | } |
| 52 | last = cur; |
| 53 | } |
| 54 | |
| 55 | void update_cnts(){ |
| 56 | vector<int> states_by_len[sz]; |