3378. Hidden Anagrams

单点时限: 10.0 sec

内存限制: 256 MB

An anagram is a word or a phrase that is formed by rearranging the letters of another. For instance, by rearranging the letters of William Shakespeare, we can have its anagrams I am a weakish speller, I'll make a wise phrase, and so on. Note that when A is an anagram of B, B is an anagram of A.

In the above examples, di erences in letter cases are ignored, and word spaces and punctuation symbols are freely inserted and/or removed. These rules are common but not applied here; only exact matching of the letters is considered.

For two strings and of letters, if a substring of is an anagram of a substring of , we call a hidden anagram of the two strings, and . Of course, is also a hidden anagram of them.

Your task is to write a program that, for given two strings, computes the length of the longest hidden anagrams of them.

Suppose, for instance, that anagram and grandmother are given. Their substrings nagr and gran are hidden anagrams since by moving letters you can have one from the other. They are the longest since any substrings of grandmother of lengths ve or more must contain d or o that anagram does not. In this case, therefore, the length of the longest hidden anagrams is four. Note that a substring must be a sequence of letters occurring consecutively in the original string and so nagrm and granm are not hidden anagrams.

输入格式

The input consists of a single test case in two lines: .

and are strings consisting of lowercase letters (a through z) and their lengths are between and , inclusive.

输出格式

Output the length of the longest hidden anagrams of and . If there are no hidden anagrams, print a zero.

样例

Input
anagram
grandmother
Output
4
Input
williamshakespeare
iamaweakishspeller
Output
18
Input
aaaaaaaabbbbbbbb
xxxxxabababxxxxxabab
Output
6
Input
abababacdcdcd
efefefghghghghgh
Output
0

3 人解决,7 人已尝试。

6 份提交通过,共有 114 份提交。

9.0 EMB 奖励。

创建: 2 年,1 月前.

修改: 2 年,1 月前.

最后提交: 1 年,7 月前.

来源: ICPC Asia Tsukuba Regional 2016

题目标签