### 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

dgarthur

#### Testers:

lbackstrom , brett1479

#### Problem categories:

Brute Force, String Manipulation