Programming Problem #15
"Light Necklaces"

Light necklaces have beads with little lights inside. Black beads (denoted by 'x') have the light permanently turned off, white beads (denoted by 'o') have the light permanently turned on, and don't-care beads (denoted by '*') can be turned on or off as desired.

Suppose that you take a light necklace, break it at some point, and hold one end in each hand. Take the bead at the end of the left half together with all adjacent beads of the same color, then do the same thing with the right half. A don't-care bead can be treated as either white or black. (All the beads taken from the left half will be the same color, and so will all the beads taken from the right half. However, the color of the 'left' beads may or may not be the same as the color of the 'right' beads.) The problem is to find a point to break the necklace that maximizes the total number of beads thus obtained.

The input consists of one or more lines, each of which contains one necklace description beginning in the first column. A necklace description is just a non-empty string of x's, o's and *'s whose length does not exceed 75. Since necklaces are circular, the last bead is adjacent to the first one. The beads in a necklace are numbered consecutively beginning with 1.

For each necklace, output a line of the form 'N after I', where N is the maximum number of beads obtainable and I is the smallest number such that breaking the necklace after bead I achieves the maximum.

Input must be read from the file "prob15.in", and output must be written to the file "prob15.out". All output to the screen will be ignored.

Example Input

<BOF>
xoxoooxxxoooooxooxxoxxxxoooox
xx*xooo*xoxoo*oox
<EOF>

Example Output

8 after 9
10 after 16
A version of this problem originally appeared in the 1992 International Olympiad in Informatics, and later appeared in the qualifying round of the 1993 U.S.A. Computing Olympiad.

Dr. Eric Shade