## Summary

In this post, I will introduce some problems related to KMP.

## OJ

Trick | Difficulty | |
---|---|---|

LC 1392 | Naive Pi | 5-6 points |

LC 796 | Pi on B + "#" + A | 3-4 points |

LC 214 | Pi on A + "#" + A[::-1] | 5-6 points |

LC 28 | Pi on B + "#" + A | 3-4 points |

## Details

### Pi

is the length of the longest prefix of substring , such that this prefix is also the suffix of . Note that this prefix excludes itself. By the definition, we have . For example, we have,

Please refer to this wiki if you want to know how the following codes work.

```
vector<int> get_pi(string const&s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1; i < n; ++i) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
pi[i] = j + (s[i] == s[j]);
}
return pi;
}
```