Analysis of a linear-time algorithm for longest palindromic substring

Question

Background

$\newcommand\ldotd{\mathinner{..}}$Last month, I heard about a new linear-time algorithm to determine the longest palindromic substring called Jeuring's algorithm. It seemed interesting, therefore I had a try to analyze the algorithm. It's not too difficult to show that it's an $\Theta(n)$-time-algorithm, but I want to observe more closely.

I wrote a C++ implementation, and an essay to prove and analyze the algorithm. It's somewhat long, therefore I will only post the critical part of the code, where you can learn the algorithm by heart, see the succeeding section. You can get all my previous work from github. pldrm.nw is the literate programming source file, which produces the pldrm.cc and pldrm.pdf. pldrm.pdf is the essay I've written.

Problem

Let $A=$ the number of times goto statement is executed in move loop, and $B=$ the number of times move loop is executed where goto statement is NOT executed, $C=$ the number of times a[++j]=min(a[p],l) is executed in move loop. You can see the code in the following section. I found that $A+B+C=2n$ and $B=\sum_{k=2}^{n+1}[b_k=1]$, where $b_k$ is the length of longest tail palindrome of $s[0\ldotd k]$, and $[P]$ is Iverson bracket. For details, you can read my pdf from github. I'm looking for somebody to help me analyze the quantity $A,C$. Any help? Thanks!

The critical part of the algorithm

Given that $s[1\ldotd n]$ is the string inputted, and $n$ is the length of $s$, where $s[0]=1,s[n+1]=0$. We say $l+r$ is the center of substring $s[l\ldotd r]$. For example, $4$ is the center of $s[2\ldotd2]$ or $s[1\ldotd3]$. $a_k$ is the length of the longest palindrome whose center is $k$, and $a[0\ldotd2n]$ is the array to save $\langle a_k\rangle$. The algorithm is used to determine $a_k$. We call some string $A$ is a tail palindrome of the other string $B$ if and only if $A$ is a palindromic tail substring of $B$. For example, $A=aba$ and $B=aaaababa$, where $A$ is palindromic and $A$ is a tail substring of $B$.

Here's the critical part of the code:

<<main loop>>=
j = 1;
l = 1;
a[0] = 1;
a[1] = 0;
for (int k=2; k<=n+1; k++) {
  <<process>>
  advance:
  ;
}
@

Process is made up of an infinite loop, which is used to find the longest tail palindrome of $s[0\ldotd k]$. There are two exits of it. One is in extension subroutine, while the other one is in move loop. The way of exit is goto advance;.

<<process>>=
for (;;) {
  <<check>>
  <<move loop>>
}
@

The check subroutine checks whether a tail palindrome of $s[0\ldotd k-1]$ could be extended to that of $s[0\ldotd k]$. If so, exit from the process loop and advance $k$, otherwise start the move loop.

<<check>>=
if (s[k] == s[k-l-1]) {
  l += 2;
  goto advance;
}
@

Here's the move loop, which looks short and easy. It's used to find a shorter tail palindrome of $s[0\ldotd k-1]$.

<<move loop>>=
a[++j] = l;
for (p=j-1; --l>=0&&l!=a[p]; p--) {
  a[++j] = min(a[p], l);
}
if (l < 0) {
  l = 1;
  goto advance;
}
@