| 15 | ll ans[maxN]; |
| 16 | |
| 17 | void extend(char c){ |
| 18 | int cur = sz++; |
| 19 | node[cur].len = node[last].len + 1; |
| 20 | int p = last; |
| 21 | while(p != -1 && !node[p].nxt.count(c)){ |
| 22 | node[p].nxt[c] = cur; |
| 23 | p = node[p].link; |
| 24 | } |
| 25 | if(p == -1){ |
| 26 | node[cur].link = 0; |
| 27 | } else { |
| 28 | int q = node[p].nxt[c]; |
| 29 | if(node[p].len + 1 == node[q].len){ |
| 30 | node[cur].link = q; |
| 31 | } else { |
| 32 | int clone = sz++; |
| 33 | node[clone].len = node[p].len + 1; |
| 34 | node[clone].nxt = node[q].nxt; |
| 35 | node[clone].link = node[q].link; |
| 36 | while(p != -1 && node[p].nxt[c] == q){ |
| 37 | node[p].nxt[c] = clone; |
| 38 | p = node[p].link; |
| 39 | } |
| 40 | node[q].link = node[cur].link = clone; |
| 41 | } |
| 42 | } |
| 43 | last = cur; |
| 44 | } |
| 45 | |
| 46 | void init(){ |
| 47 | node[0].len = 0; |