SPOJ BEADS问题后缀数组解法中拼接字符选择的疑问：为何用'}'而非'$'？

Let's break down why your choice of trailing character led to a wrong answer (WA) versus accepted (AC) solution, using concrete examples and the problem's requirements.

The Core Problem with '$' #

The BEADS problem requires that if multiple split points yield the lexicographically smallest circular string, you must choose the smallest index (starting from 1).

When you append '$' (ASCII value less than 'a') to s+s, you introduce a scenario where suffixes starting at larger indices (but still < m, the original string length) appear lexicographically smaller than those starting at smaller indices—even though their first m characters (the actual circular string) are identical.

Example: Periodic String "abab" #

For s = "abab" (m=4), s+s+'$' becomes "abababab$":

• Suffix starting at index 0: abababab$ (first 4 chars: abab)
• Suffix starting at index 2: ababab$ (first 4 chars: abab)

When comparing these two suffixes:

• The first 6 characters are identical (ababab)
• The 7th character of suffix 0 is 'a', while the 7th character of suffix 2 is '$'

Since '$' < 'a', suffix 2 is considered lexicographically smaller than suffix 0. Your suffix array will place index 2 before index 0, so your code will output 2+1=3 instead of the correct answer 0+1=1 (the smallest valid index).

Another extreme example: s = "aaaaa" (m=5). Appending '$' makes suffix 4 (aaaaa$) smaller than suffix 0 (aaaaaaaaaa$), leading your code to output 5 instead of 1.

Why '}' Works #

When you append '}' (ASCII value greater than 'z'), the opposite happens. For identical first m characters:

• Suffixes starting at smaller indices will have a lexicographically smaller full suffix, because beyond the first m characters, they still contain original string characters (which are smaller than '}') instead of hitting '}' early.

Using the same "abab" example with s+s+'}' (abababab}):

• Suffix 0's 7th character is 'a', suffix 2's 7th character is '}'
• Since 'a' < '}', suffix 0 is smaller than suffix 2, so it appears first in the suffix array. Your code picks index 0, outputting the correct answer 1.

For "aaaaa", suffix 0 will be the smallest (since its later characters are 'a's instead of '}'), so you get the correct index 0.

Key Takeaway #

When working with circular strings and suffix arrays to find the minimal rotation:

• If you need to prioritize the smallest starting index when multiple rotations are identical, append a character larger than all characters in the original string. This ensures that suffixes starting at smaller indices are considered smaller in the full suffix sort, even when their first m characters are the same.
• Appending a smaller character breaks this priority, as it makes later-starting suffixes appear smaller due to the early occurrence of the tiny character.

内容的提问来源于stack exchange，提问作者Bully Maguire