What tools/libraries are available for displaying string algorithms?

Question

I would like to write up a string algorithm similar to the image shown below, but I'm not sure which tools would be best for this.

I could use tabular for boxes or tikz to generate nodes on a grid-based system, but neither seem like the right solution for me (unless tikz has some packages for this). What tools are typically used to write text on a grid like this, optionally adding arrows, lines, and enclosing boxes?

Answer 1

This is just to say it is fairly easy to program a TikZ matrix to produce something like this. All you need to do then is to enter the rows.

\documentclass[tikz,border=3mm]{standalone}
\usetikzlibrary{matrix}
\begin{document}
\begin{tikzpicture}
 \matrix[matrix of nodes,column sep=-\pgflinewidth/2,row sep=-\pgflinewidth/2,
  cells={nodes={minimum width=1em,text height=1.5ex,
   /utils/exec=\ifnum\the\pgfmatrixcurrentcolumn<6
   \tikzset{draw}
    \ifnum\the\pgfmatrixcurrentcolumn>2
    \tikzset{fill=gray!30}
   \fi\fi}}] (mat) {
   a & b & a & b & a & c & a & & & & &\\
   & & a & b & a & b & a & c & a & & & \\
   & & & & a & b & a & b & a & c & a & \\
   & & & & & a & b & a & b & a & c & a \\
  };
\end{tikzpicture}
\end{document}

You see how that works: the positions of the cells are given by the TeX counts \pgfmatrixcurrentcolumn and \pgfmatrixcurrentrow, respectively. With /utils/exec you can define instructions that use these counts and do something with that. Here they are used to draw boxes around the 5 left-most cells (i.e. \the\pgfmatrixcurrentcolumn<6) and fill the last three of them (i.e. \ifnum\the\pgfmatrixcurrentcolumn>2).

Of course, one does not have to stop there. Here is a slightly more fancy version thereof that draws the vertical connections if the corresponding nodes exist. This is done using the execute at end matrix key, which has not yet found its way into the pgfmanual (but I suspect it will be mentioned there in the future). It also shows how you can overrule the instructions, as illustrated in the epsilon entry in which |[draw=none,fill=none]| makes sure that there is no box and no fill even though this the other nonempty nodes in this column have a filled box. The foreach keys count and remember can be found in numerous posts on this site, and are well documented in the pgf manual.

\documentclass[tikz,border=3mm]{standalone}
\usetikzlibrary{matrix}
\makeatletter% https://tex.stackexchange.com/a/85531
\long\def\ifnodedefined#1#2#3{%
    \@ifundefined{pgf@sh@ns@#1}{#3}{#2}%
}
\makeatother

\begin{document}
\begin{tikzpicture}
 \matrix[matrix of math nodes,column sep=-\pgflinewidth/2,row sep=1.5ex,
  cells={nodes={minimum width=1em,text height=1.5ex,
   /utils/exec=\ifnum\the\pgfmatrixcurrentcolumn<6
   \tikzset{draw}
    \ifnum\the\pgfmatrixcurrentcolumn>2
    \tikzset{fill=gray!30}
   \fi\fi}},execute at end matrix={
    \foreach \XX in {3,...,5}
     {\foreach \YY in {1,...,\the\numexpr\the\pgfmatrixcurrentrow-2}
      {\ifnodedefined{mat-\YY-\XX}{\ifnodedefined{mat-\the\numexpr\YY+1\relax-\XX}{%
      \draw[densely dotted] (mat-\YY-\XX) -- (mat-\the\numexpr\YY+1\relax-\XX);
      }{}}{}} }
   }] (mat) {
   a & b & a & b & a & c & a & & & & &\\
   & & a & b & a & b & a & c & a & & & \\
   & & & & a & b & a & b & a & c & a & \\
   & & & & |[draw=none,fill=none]| \varepsilon & a & b & a & b & a & c & a \\
  };
  \path foreach \X [count=\Y,remember=\X as \LastX] in {5,3,1,0} {
  (mat.west|-mat-\Y-6) node[left]{$P_\Y$}
  \ifnum\Y>1
  (mat.east|-mat-\Y-6) node[right]{$\pi[\LastX]=\X$}
  \fi};
\end{tikzpicture}
\end{document}