Round words

Time limit2sMemory limit128 MB

Summary

Given two words of length up to 2000, pick a rotation or reversal of each to maximize the LCS length and print that maximum.

Level: Hard8 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

Azamat learned about the longest common subsequence of two strings not long ago. Now he wants to know the longest common subsequence of two round words.

In a round word it makes no difference which character you start from and which direction you read in. The round word algorithm can be read as rithmalgo, and it can also be read as oglamhtir.

Read as ordinary words, algorithm and grammar have a longest common subsequence of length 3 (grm). Read as round words, the same pair reaches length 4 (grma).

You are given two round words. Choose one reading of each word, build the two strings, then measure the longest common subsequence of those strings. Write a program that reports the largest length over every choice of the two readings. Running the standard algorithm on the two words as they are written does not produce this value.

Input

The first line and the second line each contain one word. Both words are non-empty and each one is at most 2000 characters long.

Output

Print the length of the longest common subsequence of the two round words on one line, as a single integer.

Examples3

Example 1
Input
```
algorithm
grammar
```
Expected output
```
4
```
Example 2
Input
```
a
a
```
Expected output
```
1
```
Example 3
Input
```
abc
xyz
```
Expected output
```
0
```