4 substrings problem
Time Limit : 6000/3000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ○ ★
Problem Description
One day you heard the following joke
In America, you write strings.
In Soviet Russia, String writes YOU!! 1
And find that now string is writting you! So to get rid of it, you must solve the following problem:
Given a string S and its four substring a,b,c, and d. In a configuration, you can place four substrings exactly one position it occurs in S (they may overlap), and characters covered by at least one such substring is called ＾covered￣.
You should solve for minimum and maximum possible number of covered characters in a configuration.
You may assume that s contains only lowercase letters, and is of length less than 4096. However, lengths of a,b,c, and d would never exceed 64.
-------------------------------------------------------------------
1An infamous Russian reversal
In America, you write strings.
In Soviet Russia, String writes YOU!! 1
And find that now string is writting you! So to get rid of it, you must solve the following problem:
Given a string S and its four substring a,b,c, and d. In a configuration, you can place four substrings exactly one position it occurs in S (they may overlap), and characters covered by at least one such substring is called ＾covered￣.
You should solve for minimum and maximum possible number of covered characters in a configuration.
You may assume that s contains only lowercase letters, and is of length less than 4096. However, lengths of a,b,c, and d would never exceed 64.
-------------------------------------------------------------------
1An infamous Russian reversal
Input
There are several test cases.
For each test case there are 5 lines, denoting S,a,b,c, and d, respectively.
Please process until the EOF (End Of File).
For each test case there are 5 lines, denoting S,a,b,c, and d, respectively.
Please process until the EOF (End Of File).
Output
For each test case, please print a single line with two integers, first the minimum, then the maximum.
Sample Input
hello he l l o abacaba ab ba a c
Sample Output
4 5 4 6
Source
2012 ACM/ICPC Asia Regional Chengdu Online