Statistics

Problem Statement for "Homomorphism"

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

  1. "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.

  2. "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.

  3. "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.

  4. "001"

    "1010001"

    Returns: 1

    The unique non-degenerate homomorphism, h, satisfying h(001) = 1010001 is given by h(0) = 10 and h(1) = 001.

  5. "101"

    "11111111111111111111111111111111111111111111111111"

    Returns: 24

  6. "1"

    "1100111011"

    Returns: -1

  7. "000000"

    "00000111101000111101111100010111110001000100100111"

    Returns: 0

  8. "00100110"

    "011100001111001001101011000110"

    Returns: 0

  9. "110010011"

    "011110001011001110001"

    Returns: 0

  10. "0010"

    "1011011011010111010010100011111000011"

    Returns: 0

  11. "010"

    "011100"

    Returns: 1

  12. "100"

    "111011110001"

    Returns: 0

  13. "10100"

    "01001001100111111100111001110001111101111101101"

    Returns: 0

  14. "0011"

    "00001110000100101111010011110110010011"

    Returns: 0

  15. "0000110"

    "11001011010011011000111000101111100"

    Returns: 0

  16. "100010001111111010001001010001001111"

    "0101001100100010001000010011111"

    Returns: 0

  17. "00110010110101111000"

    "0"

    Returns: 0

  18. "11011"

    "11101110111011000110101000110100101"

    Returns: 0

  19. "100010001000001110111101101101111000010"

    "0100"

    Returns: 0

  20. "10110101"

    "011010110110000111100100101111"

    Returns: 0

  21. "0011010"

    "0110100000010001101111010101111100010001000001"

    Returns: 0

  22. "1001111011000010000110111111010"

    "111100000101011101111011111101"

    Returns: 0

  23. "01101001100101"

    "1101100011"

    Returns: 0

  24. "0101001001000010000110111100"

    "0100111110111"

    Returns: 0

  25. "111110001000110001100000110110000110101110"

    "01001011001"

    Returns: 0

  26. "111011101111"

    "10110110111111010111011011011111101011101101101101"

    Returns: 1

  27. "010110010100"

    "01100111011001111110110001100111011001110110001100"

    Returns: 1

  28. "110000011111111"

    "10010001000100010001000100100100100100100100100100"

    Returns: 1

  29. "00100001011111"

    "0011000110110011000110001100011011001101111111111"

    Returns: 1

  30. "00000111000"

    "101101101101101000010100000101000001010101101101"

    Returns: 1

  31. "010111"

    "01010110011101101010110011101111001110111100111011"

    Returns: 1

  32. "001101"

    "111100001111000001100010110001111100000110001"

    Returns: 1

  33. "1001010100001111100"

    "000100100001000010000100100100100000000000010010"

    Returns: 1

  34. "1000011101"

    "11111100110011001100111111111111111111110011111111"

    Returns: 1

  35. "110010"

    "000001100000011010101110101011100000011010101110"

    Returns: 1

  36. "0101011"

    "1011110100100101111010010010111101001000100"

    Returns: 1

  37. "11111011010"

    "0100001000010000100001000111010000100011101000111"

    Returns: 1

  38. "000100"

    "01010101010101010101010111011101010101010101010101"

    Returns: 4

  39. "1000111"

    "0101101010110110110010110101001011010100101101010"

    Returns: 1

  40. "011001100"

    "0000011110111000000100000111101110000001000001"

    Returns: 1

  41. "100110"

    "100001010100001010100001000010000101010000"

    Returns: 1

  42. "010000010"

    "11111101011111111111111111111111111110101111111"

    Returns: 1

  43. "000100001001"

    "111111111011100011111111111101110001111110111000"

    Returns: 1

  44. "1110110"

    "111100111100111100010001010111100111100010001010"

    Returns: 1

  45. "0000111101"

    "001111000111100011110001111001010101001111001"

    Returns: 1

  46. "00011"

    "00110000000110000000110000011110101101111010110"

    Returns: 1

  47. "00011100"

    "11111101111110111111010001100011000111111101111110"

    Returns: 1

  48. "00100"

    "00001000000001000010000101000010000000010000"

    Returns: 3

  49. "0010101"

    "1110111111011111010001110111110100011101111101000"

    Returns: 1

  50. "10110001000011110011"

    "01101011001101110110111101100110011001101101100110"

    Returns: 1

  51. "01000100"

    "1111101111111101111110111111011111111011111101"

    Returns: 1

  52. "010111100011100101011000110000011"

    "11011000011111100011110110110011111100111111111100"

    Returns: 1

  53. "011000000100"

    "100000110011000011001110101010101000001100111010"

    Returns: 1

  54. "01101011000001"

    "0110010100100110010011001010010010101010110010"

    Returns: 1

  55. "11000000100000"

    "11011001100110011001100110101100110011001100110"

    Returns: 1

  56. "01"

    "0001110100001001111000111101001000110010010100"

    Returns: 45

  57. "1"

    "01100011000001000111001011001101010001"

    Returns: -1

  58. "101101"

    "01000110000001101101000110100011000000110110100011"

    Returns: 1

  59. "0"

    "0011011010011011000101101000000010011"

    Returns: -1

  60. "1"

    "01011101101101001101001000100011"

    Returns: -1

  61. "0101"

    "01000010011101010110100001001110101011"

    Returns: 18

  62. "10"

    "011001001101100110111010000101111110"

    Returns: 35

  63. "111"

    "000000000000000000"

    Returns: -1

  64. "110"

    "001000001000011011111001110101110"

    Returns: 2

  65. "10"

    "11001001100111111101111011111011001111011101111000"

    Returns: 49

  66. "0"

    "10011010000001101110001100010001011110010111110011"

    Returns: -1

  67. "1"

    "10100011001111000100001011111110001110001010111"

    Returns: -1

  68. "11"

    "1111101100011100000111111111011000111000001111"

    Returns: -1

  69. "100"

    "1010010111001111000011100101000011100101"

    Returns: 2

  70. "11"

    "1110111110101001111111101111101010011111"

    Returns: -1

  71. "010101010101"

    "111111111111111111111111111111111111111111111111"

    Returns: 7

  72. "1110"

    "1111111111110"

    Returns: 4

  73. "110011"

    "000000111100000"

    Returns: 0

  74. "11"

    "00"

    Returns: -1

  75. "111"

    "000000000"

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: