TopCoder problem "Homomorphism" used in SRM 190 (Division II Level Three)



Problem Statement

    

A binary string is a non-empty finite sequence of 0's and 1's. Given two binary strings, u and v, their concatenation, u * v, is defined to be the binary string obtained by appending v to the end of u. For example, if u = 01100 and v = 110, then u * v = 01100110.

Consider a function, h, that maps binary strings to other binary strings. Suppose that for every string u with digits a1, a2, ..., ak in that order, it is true that h(u) = h(a1) * h(a2) * ... * h(ak). Then, h is called a non-degenerate homomorphism. In general, this means that h is uniquely determined by the values of h(0) and h(1). For example, if h(0) = 001, and h(1) = 10, then,

  • - h(110) = h(1) * h(1) * h(0) = 1010001.
  • - h(00) = h(0) * h(0) = 001001.
  • - h(0101) = h(0) * h(1) * h(0) * h(1) = 0011000110.

Create a class Homomorphism that contains a method count, which is a given a String u and a String v. The method should return the number of distinct non-degenerate homomorphisms, h, which satisfy h(u) = v. If there are infinitely many such non-degenerate homomorphisms, the method should return -1.

 

Definition

    
Class:Homomorphism
Method:count
Parameters:String, String
Returns:int
Method signature:int count(String u, String v)
(be sure your method is public)
    
 

Notes

-Two non-degenerate homomorphisms, h and h' are considered distinct if and only if h(u) is different from h'(u) for at least one binary string, u.
 

Constraints

-u and v will each contain between 1 and 50 characters inclusive.
-Each character in both u and v will be either '0' or '1'.
 

Examples

0)
    
"10"
"11001"
Returns: 4
Since h(0) and h(1) cannot be empty strings, there are precisely 4 legal non-degenerate homomorphisms:



1. h(1) = 1 and h(0) = 1001.

2. h(1) = 11 and h(0) = 001.

3. h(1) = 110 and h(0) = 01.

4. h(1) = 1100 and h(0) = 1.

1)
    
"00"
"11111"
Returns: 0
If h is a valid non-degenerate homomorphism, then h(00) = h(0) * h(0), which implies that h(00) has an even length. Thus, there are no non-degenerate homomorphisms satisfying h(00) = 11111.
2)
    
"11"
"00"
Returns: -1
Any non-degenerate homomorphism, h, satisfying h(1) = 0 will also satisfy h(11) = 00. This leaves no restrictions at all on h(0), so there are an infinite number of such non-degenerate homomorphisms.
3)
    
"001"
"1010001"
Returns: 1
The unique non-degenerate homomorphism, h, satisfying h(001) = 1010001 is given by h(0) = 10 and h(1) = 001.
4)
    
"101"
"11111111111111111111111111111111111111111111111111"
Returns: 24

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4770&pm=2363

Writer:

dgarthur

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force, String Manipulation