TopCoder problem "TheEncryptionDivOne" used in SRM 445 (Division I Level Three)



Problem Statement

    

John is obsessed with security. He is writing a letter to his friend Brus and he wants nobody else to be able to read it. He uses a simple substitution cipher to encode his message. Each letter in the message is replaced with its corresponding letter in a substitution alphabet. A substitution alphabet is a permutation of all the letters in the original alphabet. In this problem, the alphabet will consist of only lowercase and uppercase letters ('a'-'z', 'A'-'Z').

John wants to be sure that his encryption is safe, so he will not choose a cipher where a letter is encoded to either itself or to its lowercase or uppercase equivalent. For example, he will not choose a cipher where the letter 'j' is encoded to either 'j' or 'J'.

Given the original message msg and encoded message encMsg, determine the number of simple substitution ciphers that fit John's requirements and encode msg to encMsg. Return this number modulo 1234567891.

 

Definition

    
Class:TheEncryptionDivOne
Method:count
Parameters:String, String
Returns:int
Method signature:int count(String msg, String encMsg)
(be sure your method is public)
    
 

Constraints

-msg will contain between 1 and 50 characters, inclusive.
-msg and encMsg will contain the same number of characters.
-msg and encMsg both will contain only lowercase and uppercase letters ('a' - 'z', 'A' - 'Z').
 

Examples

0)
    
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
"cdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
Returns: 2
Here we have to choose how to encode to letters 'Y' and 'Z' with two letters 'a' and 'b'. There are two ways to do it.
1)
    
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
"bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY"
Returns: 1
And here John needs to encode 'Y', 'Z' with 'Z' and 'a'. He cannot map 'Z' to itself, so there is only one possible encoding.
2)
    
"topcoder"
"TOPCODER"
Returns: 0
3)
    
"thisisaveryhardproblem"
"nobodywillsolveittoday"
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10510

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13899&pm=10510

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming