Fast Pattern Matching in Strings

高速文字列パターン照合*

DONALD E. KNUTH†, JAMES H. MORRIS, JR.‡ AND VAUGHAN R. PRATT¶

要約。ある文字列内に別の与えられた文字列が出現するすべての位置を、その文字列の長さの和に比例する実行時間で発見するアルゴリズムを提示する。比例定数は、このアルゴリズムを実用に供するのに十分小さく、またこの手続きは、より一般的ないくつかのパターン照合問題を扱うよう拡張することもできる。このアルゴリズムの理論的応用により、偶数回文の連結の集合、すなわち言語$\{\alpha\alpha^R\}^*$が線形時間で認識可能であることを示す。平均的にはさらに高速に実行される他のアルゴリズムについても考察する。

キーワード。パターン、文字列、テキスト編集、パターン照合、トライメモリ、探索、文字列の周期、回文、最適アルゴリズム、フィボナッチ文字列、正規表現

テキスト編集プログラムでは、与えられた「パターン」文字列の出現を探すために、しばしば文字列を検索する必要がある。我々は、パターンがテキストの連続した部分文字列として現れるすべての位置、あるいは左端の位置だけを発見したい。例えば、$c a t e n a r y$はパターン$t e n$を含むが、$c a n a r y$を部分文字列とはみなさない。

一致するパターンを探索する明白な方法は、テキストの各開始位置で探索を試み、誤った文字が見つかった時点で探索を打ち切ることである。

Abstract. An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use, and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e., the language $\{\alpha\alpha^R\}^*$, can be recognized in linear time. Other algorithms which run even faster on the average are also considered.

Key words. pattern, string, text-editing, pattern-matching, trie memory, searching, period of a string, palindrome, optimum algorithm, Fibonacci string, regular expression

Text-editing programs are often required to search through a string of characters looking for instances of a given "pattern" string; we wish to find all positions, or perhaps only the leftmost position, in which the pattern occurs as a contiguous substring of the text. For example, catenary contains the pattern ten, but we do not regard canary as a substring.

The obvious way to search for a matching pattern is to try searching at every starting position of the text, abandoning the search as soon as an incorrect character is found. But this approach can be very inefficient, for example when we are looking for an occurrence of $aaaaaaaab$ in $aaaaaaaaaaaaaaab$. When the pattern is $a^nb$ and the text is $a^{2n}b$, we will find ourselves making $(n+1)^2$ comparisons of characters. Furthermore, the traditional approach involves "backing up" the input text as we go through it, and this can add annoying complications when we consider the buffering operations that are frequently involved.

In this paper we describe a pattern-matching algorithm which finds all occurrences of a pattern of length $m$ within a text of length $n$ in $O(m+n)$ units of time, without "backing up" the input text. The algorithm needs only $O(m)$ locations of internal memory if the text is read from an external file, and only $O(\log m)$ units of time elapse between consecutive single-character inputs. All of the constants of proportionality implied by these "O" formulas are independent of the alphabet size.

* Received by the editors August 29, 1974, and in revised form April 7, 1976. † Computer Science Department, Stanford University, Stanford, California 94305. The work of this author was supported in part by the National Science Foundation under Grant GJ 36473X and by the Office of Naval Research under Contract NR 044-402. ‡ Xerox Palo Alto Research Center, Palo Alto, California 94304. The work of this author was supported in part by the National Science Foundation under Grant GP 7635 at the University of California, Berkeley. ¶ Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139. The work of this author was supported in part by the National Science Foundation under Grant GP-6945 at University of California, Berkeley, and under Grant GJ-992 at Stanford University.

We shall first consider the algorithm in a conceptually simple but somewhat inefficient form. Sections 3 and 4 of this paper discuss some ways to improve the efficiency and to adapt the algorithm to other problems. Section 5 develops the underlying theory, and § 6 uses the algorithm to disprove the conjecture that a certain context-free language cannot be recognized in linear time. Section 7 discusses the origin of the algorithm and its relation to other recent work. Finally, § 8 discusses still more recent work on pattern matching.

1. Informal development. The idea behind this approach to pattern matching is perhaps easiest to grasp if we imagine placing the pattern over the text and sliding it to the right in a certain way. Consider for example a search for the pattern $abcabcacab$ in the text $babcbabcaabcabcabcacabc$; initially we place the pattern at the extreme left and prepare to scan the leftmost character of the input text:

↑

The arrow here indicates the current text character; since it points to $b$, which doesn’t match that $a$, we shift the pattern one space right and move to the next input character:

↑

Now we have a match, so the pattern stays put while the next several characters are scanned. Soon we come to another mismatch:

↑

At this point we have matched the first three pattern characters but not the fourth, so we know that the last four characters of the input have been $a b c x$ where $x \neq a$; we don’t have to remember the previously scanned characters, since our position in the pattern yields enough information to recreate them. In this case, no matter what $x$ is (as long as it’s not $a$), we deduce that the pattern can immediately be shifted four more places to the right; one, two, or three shifts couldn’t possibly lead to a match.

Soon we get to another partial match, this time with a failure on the eighth pattern character:

Now we know that the last eight characters were $a b c a b c a x$, where $x \neq c$. The pattern should therefore be shifted three places to the right:

We try to match the new pattern character, but this fails too, so we shift the pattern four (not three or five) more places. That produces a match, and we continue scanning until reaching another mismatch on the eighth pattern character:

Again we shift the pattern three places to the right; this time a match is produced, and we eventually discover the full pattern:

The play-by-play description for this example indicates that the pattern-matching process will run efficiently if we have an auxiliary table that tells us exactly how far to slide the pattern, when we detect a mismatch at its $j$th character $pattern[j]$. Let $next[j]$ be the character position in the pattern which should be checked next after such a mismatch, so that we are sliding the pattern $j - next[j]$ places relative to the text. The following table lists the appropriate values:

(Note that $next[j] = 0$ means that we are to slide the pattern all the way past the current text character.) We shall discuss how to precompute this table later; fortunately, the calculations are quite simple, and we will see that they require only $O(m)$ steps.

At each step of the scanning process, we move either the text pointer or the pattern, and each of these can move at most $n$ times; so at most $2n$ steps need to be performed, after the $next$ table has been set up. Of course the pattern itself doesn’t really move; we can do the necessary operations simply by maintaining the pointer variable $j$.

1. Programming the algorithm. The pattern-match process has the general form

            
              place pattern at left;
while pattern not fully matched
    and text not exhausted do
        begin
            while pattern character differs from current text character
                do shift pattern appropriately;
            advance to next character of text;
        end;
            
          

For convenience, let us assume that the input text is present in an array $text[1:n]$, and that the pattern appears in $pattern[1:m]$. We shall also assume that $m > 0$, i.e., that the pattern is nonempty. Let $k$ and $j$ be integer variables such that $text[k]$ denotes the current text character and $pattern[j]$ denotes the corresponding pattern character; thus, the pattern is essentially aligned with positions $p + 1$ through $p + m$ of the text, where $k = p + j$. Then the above program takes the following simple form:

            
              while j ≤ m and k ≤ n do
    begin
        while j > 0 and text[k] ≠ pattern[j]
            do j := next[j];
        k := k + 1; j := j + 1;
    end;
            
          

If $j > m$ at the conclusion of the program, the leftmost match has been found in positions $k - m$ through $k - 1$; but if $j \leq m$, the text has been exhausted. (The and operation here is the “conditional and” which does not evaluate the relation $text[k] \neq pattern[j]$ unless $j > 0$.) The program has a curious feature, namely that the inner loop operation “$j := next[j]$” is performed no more often than the outer loop operation “$k := k + 1$”; in fact, the inner loop is usually performed somewhat less often, since the pattern generally moves right less frequently than the text pointer does.

To prove rigorously that the above program is correct, we may use the following invariant relation: “Let $p = k - j$ (i.e., the position in the text just preceding the first character of the pattern, in our assumed alignment). Then we have $text[p + i] = pattern[i]$ for $1 \leq i < j$ (i.e., we have matched the first $j - 1$ characters of the pattern, if $j > 0$); but for $0 \leq t < p$ we have $text[t + i] \neq pattern[i]$ for some $i$, where $1 \leq i \leq m$ (i.e., there is no possible match of the entire pattern to the left of $p$).”

The program will of course be correct only if we can compute the $next$ table so that the above relation remains invariant when we perform the operation $j := next[j]$. Let us look at that computation now. When the program sets j := next[j], we know that j > 0, and that the last j characters of the input up to and including text[k] were

where $x \neq pattern[j]$. What we want is to find the least amount of shift for which these characters can possibly match the shifted pattern; in other words, we want next[j] to be the largest i less than j such that the last i characters of the input were

and $pattern[i] \neq pattern[j]$. (If no such i exists, we let next[j] = 0.) With this definition of next[j] it is easy to verify that text[t+1] ... text[k] \neq pattern[1] \ldots pattern[k-1] for k - j \leq t < k - next[j]; hence the stated relation is indeed invariant, and our program is correct.

Now we must face up to the problem we have been postponing, the task of calculating next[j] in the first place. This problem would be easier if we didn't require $pattern[i] \neq pattern[j]$ in the definition of next[j], so we shall consider the easier problem first. Let f[j] be the largest i less than j such that $pattern[1] \ldots pattern[i-1] = pattern[j-i+1] \ldots pattern[j-1]$; since this condition holds vacuously for $i = 1$, we always have $f[j] \geq 1$ when $j > 1$. By convention we let $f[1] = 0$.

The pattern used in the example of § 1 has the following f table:

If $pattern[j] = pattern[f[j]]$ then $f[j+1] = f[j]+1$; but if not, we can use essentially the same pattern-matching algorithm as above to compute $f[j+1]$, with $text = pattern!$ (Note the similarity of the $f[j]$ problem to the invariant condition of the matching algorithm. Our program calculates the largest j less than or equal to k such that $pattern[1] \ldots pattern[j-1] = text[k-j+1] \ldots text[k-1]$, so we can transfer the previous technology to the present problem.) The following program will compute $f[j+1]$, assuming that $f[j]$ and $next[1]$, ..., $next[j-1]$ have already been calculated:

The correctness of this program is demonstrated as before; we can imagine two copies of the pattern, one sliding to the right with respect to the other. For example, suppose we have established that $f[8] = 5$ in the above case; let us consider the computation of $f[9]$. The appropriate picture is

Since $pattern[8] \neq b$, we shift the upper copy right, knowing that the most recently scanned characters of the lower copy were $a\ b\ c\ a\ x$ for $x \neq b$. The $next$ table tells us to shift right four places, obtaining

and again there is no match. The next shift makes $t = 0$, so $f[9] = 1$.

Once we understand how to compute $f$, it is only a short step to the computation of $next[j]$. A comparison of the definitions shows that, for $j > 1$,

Therefore we can compute the $next$ table as follows, without ever storing the values of $f[j]$ in memory.

            
              while j < m do
    begin comment t = f[j];
        while t > 0 and pattern[j] ≠ pattern[t]
            do t := next[t];
        t := t + 1; j := j + 1;
        if pattern[j] = pattern[t]
            then next[j] := next[t]
            else next[j] := t;
    end.
            
          

This program takes $O(m)$ units of time, for the same reason as the matching program takes $O(n)$: the operation $t := next[t]$ in the innermost loop always shifts the upper copy of the pattern to the right, so it is performed a total of $m$ times at most. (A slightly different way to prove that the running time is bounded by a constant times $m$ is to observe that the variable $t$ starts at 0 and it is increased, $m - 1$ times, by 1; furthermore its value remains nonnegative. Therefore the operation $t := next[t]$, which always decreases $t$, can be performed at most $m - 1$ times.)

To summarize what we have said so far: Strings of text can be scanned efficiently by making use of two ideas. We can precompute “shifts”, specifying how to move the given pattern when a mismatch occurs at its $j$th character; and this precomputation of “shifts” can be performed efficiently by using the same principle, shifting the pattern against itself.

1. Gaining efficiency. We have presented the pattern-matching algorithm in a form that is rather easily proved correct; but as so often happens, this form is not very efficient. In fact, the algorithm as presented above would probably not be competitive with the naive algorithm on realistic data, even though the naive algorithm has a worst-case time of order $m$ times $n$ instead of $m$ plus $n$, because the chance of this worst case is rather slim. On the other hand, a well-implemented form of the new algorithm should go noticeably faster because there is no backing up after a partial match.

It is not difficult to see the source of inefficiency in the new algorithm as presented above: When the alphabet of characters is large, we will rarely have a partial match, and the program will waste a lot of time discovering rather awkwardly that $text[k] \neq pattern[1]$ for $k = 1, 2, 3, \ldots$. When $j = 1$ and $text[k] \neq pattern[1]$, the algorithm sets $j := next[1] = 0$, then discovers that $j = 0$, then increases $k$ by 1, then sets $j$ to 1 again, then tests whether or not 1 is $\leq m$, and later it tests whether or not 1 is greater than 0. Clearly we would be much better off making $j = 1$ into a special case.

The algorithm also spends unnecessary time testing whether $j > m$ or $k > n$. A fully-matched pattern can be accounted for by setting $pattern[m + 1] = "@"$ for some impossible character @ that will never be matched, and by letting $next[m + 1] = -1$; then a test for $j < 0$ can be inserted into a less-frequently executed part of the code. Similarly we can for example set $text[n + 1] = "\bot"$ (another impossible character) and $text[n + 2] = pattern[1]$, so that the test for $k > n$ needn’t be made very often. (See [17] for a discussion of such more or less mechanical transformations on programs.)

The following form of the algorithm incorporates these refinements.

            
              a := pattern[1];
pattern[m + 1] := '@'; next[m + 1] := -1;
text[n + 1] := '\bot'; text[n + 2] := a;
j := k := 1;
get started: comment j = 1;
    while text[k] ≠ a do k := k + 1;
    if k > n then go to input exhausted;
char matched: j := j + 1; k := k + 1;
loop: comment j > 0;
    if text[k] = pattern[j] then go to char matched;
    j := next[j];
    if j = 1 then go to get started;
    if j = 0 then
        begin
            j := 1; k := k + 1;
            go to get started;
        end;
    if j > 0 then go to loop;
comment text[k - m] through text[k - 1] matched;
            
          

This program will usually run faster than the naive algorithm; the worst case occurs when trying to find the pattern $ab$ in a long string of $a$'s. Similar ideas can be used to speed up the program which prepares the $next$ table.

In a text-editor the patterns are usually short, so that it is most efficient to translate the pattern directly into machine-language code which implicitly contains the $next$ table (cf. [3, Hack 179] and [24]). For example, the pattern in § 1 could be compiled into the machine-language equivalent of

L0: $k := k + 1$; L1: $\text{if } text[k] \neq a \text{ then go to L0;}$ $k := k + 1;$ $\text{if } k > n \text{ then go to input exhausted;}$ L2: $\text{if } text[k] \neq b \text{ then go to L1;}$ $k := k + 1;$ L3: $\text{if } text[k] \neq c \text{ then go to L1;}$ $k := k + 1;$ L4: $\text{if } text[k] \neq a \text{ then go to L0;}$ $k := k + 1;$ L5: $\text{if } text[k] \neq b \text{ then go to L1;}$ $k := k + 1;$ L6: $\text{if } text[k] \neq c \text{ then go to L1;}$ $k := k + 1;$ L7: $\text{if } text[k] \neq a \text{ then go to L0;}$ $k := k + 1;$ L8: $\text{if } text[k] \neq c \text{ then go to L5;}$ $k := k + 1;$ L9: $\text{if } text[k] \neq a \text{ then go to L0;}$ $k := k + 1;$ L10: $\text{if } text[k] \neq b \text{ then go to L1;}$ $k := k + 1;$

This will be slightly faster, since it essentially makes a special case for all values of j.

It is a curious fact that people often think the new algorithm will be slower than the naive one, even though it does less work. Since the new algorithm is conceptually hard to understand at first, by comparison with other algorithms of the same length, we feel somehow that a computer will have conceptual difficulties too—we expect the machine to run more slowly when it gets to such subtle instructions!

4. Extensions. So far our programs have only been concerned with finding the leftmost match. However, it is easy to see how to modify the routine so that all matches are found in turn: We can calculate the next table for the extended pattern of length m + 1 using pattern[m + 1] = "@", and then we set resume := next[m + 1] before setting next[m + 1] to −1. After finding a match and doing whatever action is desired to process that match, the sequence

will restart things properly. (We assume that text has not changed in the meantime. Note that resume cannot be zero.)

Another approach would be to leave next[m + 1] untouched, never changing it to −1, and to define integer arrays head[1 : m] and link[1 : n] initially zero, and to insert the code

at label “char matched”. The test “if $j > 0$ then” is also removed from the program. This forms linked lists for $1 \leq j \leq m$ of all places where the first $j$ characters of the pattern (but no more than $j$) are matched in the input.

Still another straightforward modification will find the longest initial match of the pattern, i.e., the maximum $j$ such that $pattern[1] \ldots pattern[j]$ occurs in $text$.

In practice, the text characters are often packed into words, with say $b$ characters per word, and the machine architecture often makes it inconvenient to access individual characters. When efficiency for large $n$ is important on such machines, one alternative is to carry out $b$ independent searches, one for each possible alignment of the pattern’s first character in the word. These searches can treat entire words as “supercharacters”, with appropriate masking, instead of working with individual characters and unpacking them. Since the algorithm we have described does not depend on the size of the alphabet, it is well suited to this and similar alternatives.

Sometimes we want to match two or more patterns in sequence, finding an occurrence of the first followed by the second, etc.; this is easily handled by consecutive searches, and the total running time will be of order $n$ plus the sum of the individual pattern lengths.

We might also want to match two or more patterns in parallel, stopping as soon as any one of them is fully matched. A search of this kind could be done with multiple next and pattern tables, with one $j$ pointer for each; but this would make the running time $kn$ plus the sum of the pattern lengths, when there are $k$ patterns. Hopcroft and Karp have observed (unpublished) that our pattern-matching algorithm can be extended so that the running time for simultaneous searches is proportional simply to $n$, plus the alphabet size times the sum of the pattern lengths. The patterns are combined into a “trie” whose nodes represent all of the initial substrings of one or more patterns, and whose branches specify the appropriate successor node as a function of the next character in the input text. For example, if there are four patterns $\{a\ b\ c\ a\ b,\ a\ b\ a\ b\ c,\ b\ c\ a\ c,\ b\ b\ c\}$, the trie is shown in Fig. 1.

Fig. 1

Such a trie can be constructed efficiently by generalizing the idea we used to calculate next$[j]$; details and further refinements have been discussed by Aho and Corasick [2], who discovered the algorithm independently. (Note that this

Therefore if we have a mismatch when $j = F_8 - 1 = 20$, our algorithm might set $j := next[j]$ for the successive values 20, 12, 7, 4, 2, 1, 0 of $j$. Since $F_k$ is $(\phi^k / \sqrt{5})$ rounded to the nearest integer, it is possible to have up to $\sim \log_\phi m$ consecutive iterations of the $j := next[j]$ loop.

We shall now show that Fibonacci strings actually are the worst case, i.e., that $\log_\phi m$ is also an upper bound. First let us consider the concept of periodicity in strings. We say that $p$ is a period of $\alpha$ if

It is easy to see that $p$ is a period of $\alpha$ if and only if

for some $k \geq 0$, where $|\alpha_1 \alpha_2| = p$ and $\alpha_2 \neq \varepsilon$. Equivalently, $p$ is a period of $\alpha$ if and only if

for some $\theta_1$ and $\theta_2$ with $|\theta_1| = |\theta_2| = p$. Condition (6) implies (7) with $\theta_1 = \alpha_2 \alpha_1$ and $\theta_2 = \alpha_1 \alpha_2$. Condition (7) implies (6), for we define $k = \lfloor |\alpha| / p \rfloor$ and observe that if $k > 0$, then $\alpha = \theta_2 \beta$ implies $\beta \theta_1 = \theta_2 \beta$ and $\lfloor |\beta| / p \rfloor = k - 1$; hence, reasoning inductively, $\alpha = \theta_2^k \alpha_1$ for some $\alpha_1$ with $|\alpha_1| < p$, and $\alpha_1 \theta_1 = \theta_2 \alpha_1$. Writing $\theta_2 = \alpha_1 \alpha_2$ yields (6).

The relevance of periodicity to our algorithm is clear once we consider what it means to shift a pattern. If $pattern[1] \ldots pattern[j-1] = \alpha$ ends with $pattern[1] \ldots pattern[i-1] = \beta$, we have

where $|\theta_1| = |\theta_2| = j - i$, so the amount of shift $j - i$ is a period of $\alpha$.

The construction of $i = next[j]$ in our algorithm implies further that $pattern[i]$, which is the first character of $\theta_1$, is unequal to $pattern[j]$. Let us assume that $\beta$ itself is subsequently shifted leaving a residue $\gamma$, so that

where the first character of $\psi_1$ differs from that of $\theta_1$. We shall now prove that

If $|\beta| + |\gamma| \geq |\alpha|$, there is an overlap of $d = |\beta| + |\gamma| - |\alpha|$ characters between the occurrences of $\beta$ and $\gamma$ in $\beta \theta_1 = \alpha = \theta_2 \psi_2 \gamma$; hence the first character of $\theta_1$ is $\gamma[d+1]$. Similarly there is an overlap of $d$ characters between the occurrences of $\beta$ and $\gamma$ in $\theta_2 \beta = \alpha = \gamma \psi_1 \theta_1$; hence the first character of $\psi_1$ is $\beta[d+1]$. Since these characters are distinct, we obtain $\gamma[d+1] \neq \beta[d+1]$, contradicting (9). This establishes (10), and leads directly to the announced result:

Theorem. The number of consecutive times that $j := next[j]$ is performed, while one text character is being scanned, is at most $1 + \log_\phi m$.

Proof. Let $L_r$ be the length of the shortest string $\alpha$ as in the above discussion such that a sequence of $r$ consecutive shifts is possible. Then $L_1 = 0, L_2 = 1$, and we have $|\beta| \geq L_{r-1}, |\gamma| \geq L_{r-2}$ in (10); hence $L_2 \geq F_{r+1} - 1$ by induction on $r$. Now if $r$ shifts occur we have $m \geq F_{r+1} \geq \phi^{r-1}$. $\Box$

The algorithm of § 2 would run correctly in linear time even if $f[j]$ were used instead of $next[j]$, but the analogue of the above theorem would then be false. For example, the pattern $a^n$ leads to $f[j] = j - 1$ for $1 \leq j \leq m$. Therefore if we matched $a^m$ to the text $a^{m-1} b \alpha$, using $f[j]$ instead of $next[j]$, the mismatch $text[m] \neq pattern[m]$ would be followed by $m$ occurrences of $j := f[j]$ and $m - 1$ redundant comparisons of $text[m]$ with $pattern[j]$, before $k$ is advanced to $m + 1$.

The subject of periods in strings has several interesting algebraic properties, but a reader who is not mathematically inclined may skip to § 6 since the following material is primarily an elaboration of some additional structure related to the above theorem.

Lemma 1. If p and q are periods of $\alpha$, and $p + q \leq |\alpha| + \gcd(p, q)$, then $\gcd(p, q)$ is a period of $\alpha$.

Proof. Let $d = \gcd(p, q)$, and assume without loss of generality that $d < p < q = p + r$. We have $\alpha[i] = \alpha[i + p]$ for $1 \leq i \leq |\alpha| - p$ and $\alpha[i] = \alpha[i + q]$ for $1 \leq i \leq |\alpha| - q$; hence $\alpha[i + r] = \alpha[i + q] = \alpha[i]$ for $1 + r \leq i + r \leq |\alpha| - p$, i.e.,

Furthermore $\alpha = \beta \theta_1 = \theta_2 \beta$ where $|\theta_1| = p$, and it follows that $p$ and $r$ are periods of $\beta$, where $p + r \leq |\beta| + d = |\beta| + \gcd(p, r)$. By induction, $d$ is a period of $\beta$. Since $|\beta| = |\alpha| - p \geq q - d \geq q - r = p = |\theta_1|$, the strings $\theta_1$ and $\theta_2$ (which have the respective forms $\beta_2 \beta_1$ and $\beta_1 \beta_2$ by (6) and (7)) are substrings of $\beta$; so they also have $d$ as a period. The string $\alpha = (\beta_1 \beta_2)^{k+1} \beta_1$ must now have $d$ as a period, since any characters $d$ positions apart are contained within $\beta_1 \beta_2$ or $\beta_1 \beta_1$.

The result of Lemma 1 but with the stronger hypothesis $p + q \leq |\alpha|$ was proved by Lyndon and Schützenberger in connection with a problem about free groups [19, Lem. 4]. The weaker hypothesis in Lemma 1 turns out to give the best possible bound: If $\gcd(p, q) < p < q$ we can find a string of length $p + q - \gcd(p, q) - 1$ for which $\gcd(p, q)$ is not a period. In order to see why this is so, consider first the example in Fig. 2 showing the most general strings of lengths 15 through 25 having both 11 and 15 as periods. (The strings are “most general” in the sense that any two character positions that can be different are different.)

abcdefghijklabcd abcdafghijklabcda abcdabghijklabcdab abcdabchijklabcdabc abcdabcdijklabcdabcd abcdabcdajklabcdabcd abcdabcdabkabcdabcdab abcdabcdabcabcdabc abcabcaabcabcabcabcabc aacaaacaaacaaacaaacaaacaa aaaaaaaaaaaaaaaaaaaaaaa

Fig. 2

Note that the number of degrees of freedom, i.e., the number of distinct symbols, decreases by 1 at each step. It is not difficult to prove that the number cannot decrease by more than 1 as we go from $|\alpha| = n - 1$ to $|\alpha| = n$, since the only new relations are $\alpha[n] = \alpha[n-q] = \alpha[n-p]$; we decrease the number of distinct symbols by one if and only if positions $n-q$ and $n-p$ contain distinct symbols in the most general string of length $n-1$. The lemma tells us that we are left with at most $\gcd(p, q)$ symbols when the length reaches $p+q-\gcd(p, q)$; on the other hand we always have exactly $p$ symbols when the length is $q$. Therefore each of the $p-\gcd(p, q)$ steps must decrease the number of symbols by 1, and the most general string of length $p+q-\gcd(p, q)-1$ must have exactly $\gcd(p, q)+1$ distinct symbols. In other words, the lemma gives the best possible bound.

When $p$ and $q$ are relatively prime, the strings of length $p+q-2$ on two symbols, having both $p$ and $q$ as periods, satisfy a number of remarkable properties, generalizing what we have observed earlier about Fibonacci strings. Since the properties of these pathological patterns may prove useful in other investigations, we shall summarize them in the following lemma.

Lemma 2. Let the strings $\sigma(m, n)$ of length $n$ be defined for all relatively prime pairs of integers $n \geq m \geq 0$ as follows:

if $0 < m < n$.

These strings satisfy the following properties: (i) $\sigma(m, qm+r)\sigma(m-r, m) = \sigma(r, m)\sigma(m, qm+r),$ for $m > 2$; (ii) $\sigma(m, n)$ has period $m$, for $m > 1$; (iii) $c(\sigma(m, n)) = \sigma(n-m, n)$, for $n > 2$. (The function $c(\alpha)$ was defined in connection with (3) above.)

Proof. We have, for $0 < m < n$ and $q \geq 2$,

hence, if $\theta_1 = \sigma(n \bmod m, m)$ and $\theta_2 = \sigma(m, n)$ and $q \geq 1$,

It follows that

which combine to prove (i). Property (ii) also follows immediately from (12), except for the case $m = 2, n = 2q+1, \sigma(2, 2q+1) = (ab)^q a$, which may be verified directly. Finally, it suffices to verify property (iii) for $0 < m < \frac{1}{2} n$, since $c(c(\alpha)) = \alpha$; we must show that

When $m \leq 2$ this property is easily checked, and when $m > 2$ it is equivalent by induction to

Set $n \mod m = r,\ [n/m] = q$, and apply property (i). $\Box$

By properties (ii) and (iii) of this lemma, $\sigma(p, p+q)$ minus its last two characters is the string of length $p+q-2$ having periods $p$ and $q$. Note that Fibonacci strings are just a very special case, since $\phi_n = \sigma(F_{n-1}, F_n)$. Another property of the $\sigma$ strings appears in [15]. A completely different proof of Lemma 1 and its optimality, and a completely different definition of $\sigma(m, n)$, were given by Fine and Wilf in 1965 [7]. These strings have a long history going back at least to the astronomer Johann Bernoulli in 1772; see [25, § 2.13] and [21].

If $\alpha$ is any string, let $P(\alpha)$ be its shortest period. Lemma 1 implies that all periods $q$ which are not multiples of $P(\alpha)$ must be greater than $|\alpha| - P(\alpha) + \gcd(q, P(\alpha))$. This is a rather strong condition in terms of the pattern matching algorithm, because of the following result.

Lemma 3. Let $\alpha = \text{pattern}[1] \ldots \text{pattern}[j-1]$ and let $a = \text{pattern}[j]$. In the pattern matching algorithm, $f[j] = j - P(\alpha)$, and $\text{next}[j] = j - q$, where $q$ is the smallest period of $\alpha$ which is not a period of $\alpha a$. (If no such period exists, $\text{next}[j] = 0$.) If $P(\alpha)$ divides $P(\alpha a)$ and $P(\alpha a) < j$, then $P(\alpha) = P(\alpha a)$. If $P(\alpha)$ does not divide $P(\alpha a)$ or if $P(\alpha a) = j$, then $q = P(\alpha)$.

Proof. The characterizations of $f[j]$ and $\text{next}[j]$ follow immediately from the definitions. Since every period of $\alpha a$ is a period of $\alpha$, the only nonobvious statement is that $P(\alpha) = P(\alpha a)$ whenever $P(\alpha)$ divides $P(\alpha a)$ and $P(\alpha a) \neq j$. Let $P(\alpha) = p$ and $P(\alpha a) = mp$; then the $(mp)$th character from the right of $\alpha$ is $a$, as is the $(m-1)p$th, $\ldots$, as is the $p$th; hence $p$ is a period of $\alpha a$. $\Box$

Lemma 3 shows that the $j := \text{next}[j]$ loop will almost always terminate quickly. If $P(\alpha) = P(\alpha a)$, then $q$ must not be a multiple of $P(\alpha)$; hence by Lemma 1, $P(\alpha) + q \geq j + 1$. On the other hand $q > P(\alpha)$; hence $q > \frac{1}{2}j$ and $\text{next}[j] < \frac{1}{2}j$. In the other case $q = P(\alpha)$, we had better not have $q$ too small, since $q$ will be a period in the residual pattern after shifting, and $\text{next}[\text{next}[j]]$ will be $< q$. To keep the loop running it is necessary for new small periods to keep popping up, relatively prime to the previous periods.

1. Palindromes. One of the most outstanding unsolved questions in the theory of computational complexity is the problem of how long it takes to determine whether or not a given string of length $n$ belongs to a given context-free language. For many years the best upper bound for this problem was $O(n^3)$ in a general context-free language as $n \to \infty$; L. G. Valiant has recently lowered this to $O(n^{\log_2 7})$. On the other hand, the problem isn’t known to require more than order $n$ units of time for any particular language. This big gap between $O(n)$ and $O(n^{2.81})$ deserves to be closed, and hardly anyone believes that the final answer will be $O(n)$.

Let $\Sigma$ be a finite alphabet, let $\Sigma^*$ denote the strings over $\Sigma$, and let

Here $\alpha^R$ denotes the reversal of $\alpha$, i.e., $(a_1 a_2 \ldots a_n)^R = a_n \ldots a_2 a_1$. Each string $\pi$ in $P$ is a palindrome of even length, and conversely every even palindrome over

Σ is in P. At one time it was popularly believed that the language $P^*$ of “even palindromes starred”, namely the set of palstars $\pi_1 \ldots \pi_n$ where each $\pi_i$ is in $P$, would be impossible to recognize in $O(n)$ steps on a random-access computer.

It isn’t especially easy to spot members of this language. For example, $a a b b a b b a$ is a palstar, but its decomposition into even palindromes might not be immediately apparent; and the reader might need several minutes to decide whether or not

is in $P^*$. We shall prove, however, that palstars can be recognized in $O(n)$ units of time, by using their algebraic properties.

Let us say that a nonempty palstar is prime if it cannot be written as the product of two nonempty palstars. A prime palstar must be an even palindrome $\alpha \alpha^R$ but the converse does not hold. By repeated decomposition, it is easy to see that every palstar $\beta$ is expressible as a product $\beta_1 \ldots \beta_t$ of prime palstars, for some $t \geq 0$; what is less obvious is that such a decomposition into prime factors is unique. This “fundamental theorem of palstars” is an immediate consequence of the following basic property.

Lemma 1. A prime palstar cannot begin with another prime palstar.

Proof. Let $\alpha \alpha^R$ be a prime palstar such that $\alpha \alpha^R = \beta \beta^R \gamma$ for some nonempty even palindrome $\beta \beta^R$ and some $\gamma \neq \varepsilon$; furthermore, let $\beta \beta^R$ have minimum length among all such counterexamples. If $|\beta \beta^R| > |\alpha|$ then $\alpha \alpha^R = \beta \beta^R \gamma = \alpha \delta \gamma$ for some $\delta \neq \varepsilon$; hence $\alpha^R = \delta \gamma$, and $\beta \beta^R = (\beta \beta^R)^R = (\alpha \delta)^R = \delta^R \alpha^R = \delta^R \delta \gamma$, contradicting the minimality of $|\beta \beta^R|$. Therefore $|\beta \beta^R| \leq |\alpha|$; hence $\alpha = \beta \beta^R \delta$ for some $\delta$, and $\beta \beta^R \gamma = \alpha \alpha^R = \beta \beta^R \delta \delta^R \beta \beta^R$. But this implies that $\gamma$ is the palstar $\delta \delta^R \beta \beta^R$, contradicting the primality of $\alpha \alpha^R$. $\Box$

Corollary (Left cancellation property.) If $\alpha \beta$ and $\alpha'$ are palstars, so is $\beta$.