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