We're given two strings, ~S~ and ~T~, containing only uppercase English characters (
If a character at index ~i~ of string ~S~ is the same as the character at index ~j~ of string ~T~, the two strings may cross at those indices. We define this as a string crossing.
Here is a visual example of a string crossing:
G O HELLOWORLD D B Y E
You are allowed to modify up to one character in string ~T~ by changing the character at any index to another uppercase English character.
Your job is to determine the maximum number of string crossings after modifying up to one character in string ~T~.
For this problem, you will NOT be required to pass all the samples to receive points, and you are NOT required to pass all previous subtasks to receive points for a specific subtask.
~1 \le |S|, |T| \le 10^6~
~|X|~ represents the length of a string ~X~.
Subtask 1 [6/15]
~1 \le |S|, |T| \le 500~
Subtask 2 [4/15]
~S~ and ~T~ will only contain the characters
Subtask 3 [5/15]
No additional constraints.
The first line will contain ~|S|~ and ~|T|~, space-separated.
The second line will contain ~S~.
The third and final line will contain ~T~.
Output one integer on one line, the maximum number of string crossings after modifying up to one character in string ~T~.
10 7 HELLOWORLD GOODBYE
Without any modifications, we can count ~6~ string crossings.
If we change the
GOODBYE to an
L, we can now count ~9~ crossings.