KMP、manachar、Z algorithm

/* KMP

文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか

s:aabaabaac
A:_010123450

string s = "aabaabaac";
ll A[55];
A[0] = -1;
int j = -1;
for (int i = 0; i < s.size(); i++) {
  while (j >= 0 && s[i] != s[j]) j = A[j];
  j++;
  A[i+1] = j;
}
*/

/* manachar

その文字を中心にた回文の半径を求める。
偶数長回文は「a$a$b$a$a$b$a$a$c」などする。

s:aabaabaac
R:113113111 

string s = "aabaabaac";
ll R[55];
int i = 0, j = 0;
while (i < s.size()) {
  while (i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]) ++j;
  R[i] = j;
  int k = 1;
  while (i - k >= 0 && i + k < s.size() && k + R[i - k] < j) R[i + k] = R[i - k], ++k;
  i += k; j -= k;
}
*/

/* z algorithm

s と s[i:|s|-1] の最長共通接頭辞の長さ

s:aabaabaac
Z:910510210 

string s = "aabaabaac";
ll Z[55];
Z[0] = s.size();
int i = 1, j = 0;
while (i < s.size()) {
  while (i + j < s.size() && s[j] == s[i + j]) ++j;
  Z[i] = j;
  if (j == 0) { ++i; continue;}
  int k = 1;
  while (i + k < s.size() && k + Z[k] < j) Z[i + k] = Z[k], ++k;
  i += k; j -= k;
}
*/