Bracelets

Time limit30sMemory limit256 MB

Summary

Given two circular strings, find the longest common subsequence that can be read in the same or opposite orientation on the two bracelets, and report twice its length.

Level: Medium7 of 10
Topics: Dynamic programming, String, Divide and conquer, Implementation
Solved: No attempts yet

Problem

Megamind has finally devised the perfect plan to take down his arch-nemesis, Metro Man. He has designed a pair of circular power bracelets, one for his left wrist and one for his right. On each bracelet he has inscribed a sequence of magical glyphs (symbols); every glyph that is activated increases Megamind's strength by the might of one grizzly bear.

There is a catch: the bracelets only work when the subsequences of glyphs activated on the two bracelets are identical. For example, suppose the glyphs on the two bracelets are given by the strings “metrocity” and “kryptonite”. Then the best activation gives Megamind the power of 10 grizzly bears: on the first bracelet the letters “etoty” are activated in clockwise order, and the same letters are activated in counterclockwise order on the second bracelet. Because 5 glyphs are activated on each bracelet, the total power is $5 + 5 = 10$ .

In general the order of the activated letters matters, but the orientation in which each bracelet's activated subsequence is read (clockwise or counterclockwise) may or may not be the same on the two bracelets. And remember that the bracelets are circular, so the reading may begin at any position.

Determine the maximum power (measured in grizzly bears) that Megamind can achieve by activating glyphs on both bracelets.

Input

The input consists of several test cases: at most 100 of them, of which at most 5 are “large”. Each test case is given on a single line containing a space-separated pair of strings $s$ and $t$ , describing the sequences of glyphs on Megamind's left and right bracelets, respectively. Each string consists only of lowercase English letters (‘a’–‘z’). The length of each string is between $1$ and $100$ inclusive, except in the large test cases, where the length of each string is between $1$ and $1500$ inclusive. Input continues until the end of file.

Output

For each test case, print on its own line the maximum power (in grizzly bears) Megamind can achieve by activating glyphs on his two bracelets.

Examples8

Example 1

Input

metrocity kryptonite
megamind agemdnim
metroman manmetro
megamindandmetroman metromanandmegamind

Expected output

Example 2
Input
```
a a
a b
z z
q q
```
Expected output
```
2
0
2
2
```
Example 3
Input
```
abc xyz
abc abc
```
Expected output
```
0
6
```
Example 4
Input
```
ba ab
```
Expected output
```
4
```
Example 5
Input
```
abc cba
```
Expected output
```
6
```
Example 6
Input
```
abcdef defabc
```
Expected output
```
12
```
Example 7
Input
```
aaaa aa
aaaa aaaa
ab abab
```
Expected output
```
4
8
4
```
Example 8
Input
```
abcde edcba
abcd dcba
```
Expected output
```
10
8
```