{"raw_statement":[{"iden":"statement","content":"Finally, Megamind has devised the perfect plan to take down his arch-nemesis, Metro Man! Megamind has designed a pair of circular power bracelets to be worn on his left and right wrists. On each bracelet, he has inscribed a sequence of magical glyphs (symbols); each activated glyph augments Megamind’s strength by the might of one grizzly bear!\n\nHowever, there’s a catch: the bracelets only work when the subsequences of glyphs activated on each bracelet are identical. For example, given a pair of bracelets whose glyphs are represented by the strings “metrocity” and “kryptonite”, then the optimal activation of glyphs would give Megamind the power of 10 grizzly bears:\n\nOn the first bracelet, the letters “etoty” are activated in clockwise order; the same letters are activated in counterclockwise order on the second bracelet. Generally, the ordering of the letters is important, but the orientation of the activated subsequence on each bracelet (i.e., clockwise or counterclockwise) may or may not be the same—and don’t forget that the bracelets are circular!\n\nHelp Megamind defeat Metro Man by determining the optimal subsequences of glyphs needed to activate his bracelets.\n\nThe input file will contain one space-separated pair of strings s and t, corresponding to the sequences of glyphs on Megamind’s left and right power bracelets, respectively. Each string will consist of only lowercase letters (‘a’-‘z’). The length of each input string will be between 1 and 1500 characters, inclusive.\n\nPrint a single integer: the maximum power (in units of grizzly bears) that Megamind will be able to achieve by activating glyphs on his bracelets.\n\n"},{"iden":"input","content":"The input file will contain one space-separated pair of strings s and t, corresponding to the sequences of glyphs on Megamind’s left and right power bracelets, respectively. Each string will consist of only lowercase letters (‘a’-‘z’). The length of each input string will be between 1 and 1500 characters, inclusive."},{"iden":"output","content":"Print a single integer: the maximum power (in units of grizzly bears) that Megamind will be able to achieve by activating glyphs on his bracelets."},{"iden":"examples","content":"Inputmetrocity kryptoniteOutput10Inputmegamind agemdnimOutput16Inputmetroman manmetroOutput16Inputmegamindandmetroman metromanandmegamindOutput32"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s, t \\in \\Sigma^* $ be two strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $, representing the circular sequences of glyphs on the left and right bracelets, respectively.  \nLet $ |s| = n $, $ |t| = m $, with $ 1 \\leq n, m \\leq 1500 $.\n\n**Constraints**  \n- The bracelets are circular: any substring may be taken starting at any position and wrapping around.  \n- A valid activated subsequence on each bracelet is a subsequence (not necessarily contiguous) that appears in the circular string in some rotational order (clockwise or counterclockwise).  \n- The subsequences activated on both bracelets must be identical in sequence of characters.\n\n**Objective**  \nFind the length of the longest common subsequence (LCS) that can be formed between any circular rotation of $ s $ and any circular rotation of $ t $, where each string may be read in either clockwise or counterclockwise direction.  \n\nThat is, compute:  \n$$\n\\max_{\\substack{r_1 \\in \\text{Rot}(s) \\\\ r_2 \\in \\text{Rot}(t) \\\\ d_1, d_2 \\in \\{+1, -1\\}}} \\text{LCS}(r_1^{d_1}, r_2^{d_2})\n$$  \nwhere $ \\text{Rot}(x) $ denotes the set of all rotations of string $ x $, and $ r^d $ denotes the string $ r $ read in direction $ d $ ($ +1 $: forward, $ -1 $: reversed).\n\nEquivalently, since reversing a circular string is equivalent to reversing the direction of traversal, we may equivalently consider:  \n$$\n\\max_{\\substack{u \\in \\text{Circ}(s) \\\\ v \\in \\text{Circ}(t)}} \\text{LCS}(u, v)\n$$  \nwhere $ \\text{Circ}(x) $ denotes the set of all linear strings obtainable by cutting the circular string $ x $ at any point and reading in either direction (i.e., all rotations and their reverses).\n\nThus, the problem reduces to:  \n$$\n\\max \\left\\{ \\text{LCS}(u, v) \\mid u \\in \\{ s[i:] + s[:i], \\text{reverse}(s[i:] + s[:i]) \\mid 0 \\leq i < n \\},\\ v \\in \\{ t[j:] + t[:j], \\text{reverse}(t[j:] + t[:j]) \\mid 0 \\leq j < m \\} \\right\\}\n$$","simple_statement":"Find the length of the longest common subsequence between two circular strings, where one string can be read clockwise and the other counterclockwise.","has_page_source":false}