| 16 | if(cur == -1) return false; cur = next[cur][other[i]]; } |
| 17 | return true; } |
| 18 | void extend(char c){ int cur = sz++; len[cur] = len[last]+1; |
| 19 | next[cur].clear(); isclone[cur] = false; int p = last; |
| 20 | for(; p != -1 && !next[p].count(c); p = link[p]) |
| 21 | next[p][c] = cur; |
| 22 | if(p == -1){ link[cur] = 0; } |
| 23 | else{ int q = next[p][c]; |
| 24 | if(len[p] + 1 == len[q]){ link[cur] = q; } |
| 25 | else { int clone = sz++; isclone[clone] = true; |
| 26 | len[clone] = len[p] + 1; |
| 27 | link[clone] = link[q]; next[clone] = next[q]; |
| 28 | for(; p != -1 && next[p].count(c) && next[p][c] == q; |
| 29 | p = link[p]){ |
| 30 | next[p][c] = clone; } |
| 31 | link[q] = link[cur] = clone; |
| 32 | } } last = cur; } |
| 33 | void count(){ |
| 34 | cnt=vi(sz, -1); stack<ii> S; S.push(ii(0,0)); |
| 35 | map<char,int>::iterator i; |