(p, back=False)
| 3 | import string |
| 4 | |
| 5 | def compute_prefix_function(p, back=False): |
| 6 | n = len(p) |
| 7 | next = np.zeros(n, dtype=int) |
| 8 | k = -1 |
| 9 | j = 0 |
| 10 | next[0] = -1 |
| 11 | while j < n-1: |
| 12 | if k == -1 or p[j] == p[k]: |
| 13 | k+=1 |
| 14 | j+=1 |
| 15 | next[j] = k |
| 16 | if back: |
| 17 | print("next[%s]=%s"%(str(j), str(k))) |
| 18 | else: |
| 19 | if back: |
| 20 | print("back:", p[j], p[k], k, "->", next[k]) |
| 21 | k = next[k] |
| 22 | return next |
| 23 | |
| 24 | def check_next(next): |
| 25 | last = -2 |