Statistics

Problem Statement for "Substreeng"

Problem Statement

Hero has a tree. As usual, the tree has n vertices labeled 0 through n-1. Each edge of the tree has a one-character label. You are given the description of the tree: a int[] par and a String ch with n-1 elements each. For each valid i, the tree contains an edge between vertices (i+1) and par[i], and the label on the edge is ch[i]. For any ordered pair of vertices (x,y), the (x,y)-label is obtained as follows: Consider the unique simple path from x to y. For each edge on this path write down its label. The (x,y)-label is the concatenation of those edge labels, in order. We say that the tree contains a string S if there is a pair of vertices (x,y) such that S is the (x,y)-label. You are given a String pat. This string has a particular property: there are no adjacent equal characters in pat. Hero wants to choose a subtree of his tree. (A subtree is any nonempty connected subgraph. Two subtrees are distinct if their sets of vertices differ.) The chosen subtree should not contain the string pat. Count the number of ways in which Hero can choose his subtree, and return that count modulo 10^9 + 7.

Definition

Class:
Substreeng
Method:
count
Parameters:
int[], String, String
Returns:
int
Method signature:
int count(int[] par, String ch, String pat)
(be sure your method is public)

Constraints

  • par will contain between 1 and 100 elements, inclusive.
  • For each valid i, par[i] will be between 0 and i, inclusive.
  • par and ch will contain the same number of elements.
  • Each character in ch will be between 'a' and 'z', inclusive.
  • pat will contain between 1 and 8 characters, inclusive.
  • Each character in pat will be between 'a' and 'z', inclusive.
  • There will be no equals adjacent characters in pat.

Examples

  1. {0,0,0}

    "aab"

    "ab"

    Returns: 8

    This tree contains the edges 1-0 (label 'a'), 2-0 (label 'a'), and 3-0 (label 'b'). Hero can choose a subtree that corresponds to one of the following 8 subsets of vertices: {0}, {1}, {2}, {3}, {0,1}, {0,2}, {0,1,2}, or {0,3}.

  2. {0,0,0}

    "aaa"

    "b"

    Returns: 11

    This tree has 11 different subtrees (including the tree itself), and Hero can choose any of them.

  3. {0,1,2,3}

    "abab"

    "ab"

    Returns: 9

  4. {0,1,2,3,4,5,6,7,8}

    "ababababa"

    "c"

    Returns: 55

  5. {0,1,2,3,4,5,6,7,8}

    "ababababa"

    "abab"

    Returns: 34

  6. {0,1,1,3,1,5,6,1,8,9,10,1,12,13,14,15,1,17,18,19,20,21,1,23,24,25,26,27,28,0,30,30,32,30,34,35,30,37,38,39,30,41,42,43,44,30,46,47,48,49,50,30,52,53,54,55,56,57,1,59,59,61,59,63,64,59,66,67,68,59,70,71,72,73,59,75,76,77,78,79,59,81,82,83,84,85,86}

    "abbababbababababbabababababababbababbababababbababababababbaababaababababaababababababa"

    "abababab"

    Returns: 645719518

  7. {0,1,1,3,1,5,6,1,8,9,10,1,12,13,14,15,1,17,18,19,20,21,1,23,24,25,26,27,28,0,30,30,32,30,34,35,30,37,38,39,30,41,42,43,44,30,46,47,48,49,50,30,52,53,54,55,56,57,1,59,59,61,59,63,64,59,66,67,68,59,70,71,72,73,59,75,76,77,78,79,59,81,82,83,84,85,86}

    "abbababbababababbabababababababbababbababababbabababababababbababbababababbabababababab"

    "abababa"

    Returns: 428915107

  8. {0,1,2,3,4,5,6,0,8,9,10,11,12,13,0,15,16,17,18,19,20,0,22,23,24,25,26,27,0,29,30,31,32,33,34,0,36,37,38,39,40,41,0,43,44,45,46,47,48,0,50,51,52,53,54,55,0,57,58,59,60,61,62,0,64,65,66,67,68,69,0,71,72,73,74,75,76,0,78,79,80,81,82,83,0,85,86,87,88,89,90,0,92,93,94,95,96,97}

    "babababbababababababaababababababababababaabababaabababaabababaabababababababbabababbabababbababab"

    "abababab"

    Returns: 315996839

  9. {0,1,1,2,3,4,6,1,2,1,8,1,10,13,2,11,13,9,12,2,6,6,8,21,16,10,23,15,5,11,6,13,13,31,14}

    "dcddcbbabdbadacbbddbbcadccacacaacbc"

    "cb"

    Returns: 571267

  10. {0,0,1,0,0,4,5,3,1,4,0,2,0,7,13,6,8,15,11,13,14,19,11,0,5,15,11,5,27,11}

    "baaabbbbaaababbbabaaabaaabbbbb"

    "babababa"

    Returns: 2615496

  11. {0,1,2,3,0,3,4,6,4,6,2,4,7,11,3,15,16,4,16,14,11,19,14,2,0,18,10,19,16,13,3,19,20,7,30,29,21,14,35,16,34,21,3,13,4,0,3,15,1,8,30,5,43,32,5,45,15,17,20,27}

    "cdaaccaacbbcbbaccacdcbcddaadccadacccdbbcaabccdbdbaabdaacdbba"

    "bd"

    Returns: 8582407

  12. {0,1,1,2,2,3,4,4,2,4,3,5,8,11,13,4,5,7,14,9,7,8,15,12,18,9,20,19,10,16,9,17,10,29,21,25,8,15,21,16,37,19,21,2,35,20,19,37,5,21,23,43,20,1,0,5,0,20,3,5,43,42,34,38,51,64,12,64,12,62,29,1,60,26,73,54,32,53,64,39,0,16,9,26,70,9}

    "babcccbcaccbcbcaacacbccbacbccbccaccbcbcabbbccabaacaccbcccbccaccbbcbcccbbccbacbcbcbbcba"

    "cbac"

    Returns: 961749080

  13. {0,0,1,1,0,5,0,3,1,8,3,9,4,6,0,15,14,2,3,7,1,6,8,8,2,12,15,12,25,1,27,13,10,32,7,16,35,34,34,11,15,11,40,4,0,20,14,19,40,1,47,49,1,1,38,50,43,15,31,0,11,53,35,24,52,14,45,8,68,47,63,26,6,6,18,24,1,66,64,64,37,48,13,34,38,37,24,72}

    "aaabaabaccbcaaccaabcbbaccacbabbcccaccbcabcacabbaacccacbbabbabcccababcacababacccbacacabcb"

    "cbab"

    Returns: 84404027

  14. {0,0,1,1,0,3,6,6,7,3,9,3,12,8,8,15,4,14,5,4,1,13,11,15,8,16,3,21,5,1,7,3,6,17,20,21,18,5,32,15,32,23,41,40,21,24,14,30,17,27,4,39,24,0,0,15,21,8,31,41,32,2,32,50,6,33,16,60,12,59}

    "bdacacbdddccdaadabdbaccbcdbbababaccbdaaadcdbdddabdbaddadbbdbbacaabccac"

    "bdc"

    Returns: 643096950

  15. {0,1,2,2,0,0,4,5,1,8,2,11,4,0,9,11,11,2,8,5,6,3,9,16,9,25,9,18,13,3,22,28,3,14,21,26,14,33,34,25,3,34,25,41,5,28,25,5,42,44,45,48,33,4,22,11,39,29,58,21,46,27,3,26,60,0,34,10}

    "bbaaaabababaaabbbaaaaaabbababbabbaabaaabbbababbbbbaabbabaababaabbbbb"

    "ba"

    Returns: 2891

  16. {0,1,0,3,0,3,0,0,2,4,3,10,5,8,10,7,9,7,8,19,16,4,4,20,2,10,13,17,13,18,14,14,7,11,28,20,25,18,1,5,39,21,24,31,8,35,20,41,23,29,39,50,23,49,11,8,27,11,58,28,22,52,0,21,51}

    "aaaabbaaabababbababbabbaaaabbbaaaabaaabaaabaabababaaababbabaabaaa"

    "bababab"

    Returns: 191900864

  17. {0,1,0,2,2,4,1,2,7,8,2,8,11,11,5,2,8,4,15,0,6,16,22,11,17,1,2,18,4,14,7,4,0,2,13,27,21,7,7,15,28,4,14,25,14,7,10,1,46,49,27,18,17,0,33,21,23,17,52,37,58,55,13,58,19,43,50,27,21,37,64,65,68,26,70,72,76,15,54,32,67,34,60}

    "aabaaacabbaababbbbbcabaaaaaabacbbaabbaabbcacabbcbbcaabbcbaaaaacbabcaacaaacaacbcccbc"

    "ababcbc"

    Returns: 413430447

  18. {0,1,0,3,3,3,6,2,7,0,3,10,1,2,0,4,9,3,9,3,16,13,13,12,16,8,7,0,13,26,30,9,23,3,2,32,32,8,9,38,6,25,28,17,30,12,43,34,23,42,26,9,45,33,27,17,14,16,43,32,16,39,29,57,32,30,32,16,1,0,19,5,66,63,20,29,17,30,26,22,42,54,25,74}

    "abababaaaaaababbbabbaaaabbababbbbaabaaaaabaababbaaaabaaaababaabbbbbbaaabbabbaaabbaab"

    "a"

    Returns: 381

  19. {0,0,1,0,1,0,0,0,6,5,5,4,7,7,12,10,0,14,18,11,16,7,22,12,22,20,10,22,28,18,30,2,23,23,19,0,7,6,20,7,40,9,13,14,27,28,42,42,18,19,48,32,11,5,18,52,39,48,27,34,42,10,1,36,10,14,53,8,57,28,52,59,26,62,67,58,46,7,1,49,40,24,70,53}

    "daaccdcbcdbbdcabdabbaadbcaddbcadcacbbbacdbacbddbbaaaddccddcabbbbbcccaddbcdbcbbbccdaa"

    "cbdbdbcd"

    Returns: 16934051

  20. {0,1,0,2,1,2,4,4,4,0,4,5,5,1,1,15,12,17,4,6,16,3,0,1,21,15,17,20,19,15,30,14,27,8,34,1,3,33,5,8,35,2,17,36,36,10,11}

    "cbaccbbbbcccccaccbccaaaababaaccccccbbbbbbabacaa"

    "bc"

    Returns: 33427

  21. {0,0,2,1,3,0,2,1,5,9,1,10,6,7,10,5,12,16,1,7,8,2,2,11,10,17,21,27,18,1,7,21,19,31,21,0,23,26,7,22,20,2,26,25,23,44,23,41,42,31,37,48,16,15,33,41,39,24,6,5,17,32,27,23,5,59,11,21,42,56,35,31,36,70,30,48,5,63,33,51,0,25,50,72,81}

    "bdddbadbcadaadbdadacabadcbcaabcaaaacbaccbbadaaddcbabadabbaadcdcbcaacabcccddbddaddbdbb"

    "bdcbd"

    Returns: 228310929

  22. {0,1,0,0,4,2,4,7,1,7,5,0,3,2,14,6,16,14,11,5,10,2,12,21,5,12,20,22,9,5,20,28,26,14,20,15,9,8,2,5,13,37,25,15,14}

    "cdbcbbccaadaabdcabdbaddbdbbbbcdbcadddbcdcaccd"

    "cacdca"

    Returns: 87686149

  23. {0,1,2,1,3,2,3,6,1,5,6,0,4,7,8,11,0,9,4,10,19,16,11,18,20,20,6,19,6,21,25,22,0,3,32,7,7,32,36,19,20,13,27,36,5,14,0,28,24,27,27,51,45,7,0,5,15,10,12,20,52,17,16,42,9,60,41,53,39,69,31,6,4,39,39,55,74,41,41}

    "bbbbbabbbaabbbbbaaaabbabbbabbababbabbbaaaabaabaabbababaaaabbbbbbabbabbbababaaab"

    "b"

    Returns: 236

  24. {0,1,1,0,1,1,0,3,7,9,2,3,3,11,5,2,7,12,18,18,15,13,10,5,15,15,25,13,21,1,19,14,11,17,18,3,21,6,11,22,6,6,26,36,12,13,25,8,13,42,9,39,27,36,27,53,1,49,35,25,49,45,33,46,41,41,40,32,9,13,57,53,44,51,52,2}

    "bcaabcbdabcdddbccdadbdcadcccadadabaacadacddbdcccaccbbcabbacdbbbadbdcadbacaad"

    "abcbdada"

    Returns: 755049304

  25. {0,0,0,2,3,1,2,6,5,7,10,3,11,1,10,15,7,5,6,19,17,14,14,5,1,18,10,13,23,0,16,5,10,15,12,31,32,31,24,19,6,32,14,41,13,21,20,12,8,22,16,16,15,29,31,38,16,49,40,21,60,60,47,58,26,39,60,51,62,12,55,25,62,57,51,45,31,45,44,68,57,14,8,81,47,75,36,51,77,8,49,46,59,20}

    "bbbbbbababbbbababbabaababaabababaabbababaababbbaaababbaaaaabbabbbbbaaabbaabaabaabaababbbababba"

    "babababa"

    Returns: 5290347

  26. {0,0,1,0,2,0,0,2,7,2,3,3,0,7,6,3,6,10,5,5,13,17,3,16,0,22,23,25,15,18,20,22,7,27,2,5,6,33,30,22,38,30,1,31,33,45,30,7,11,25,43,33,34,23,42,42,37,39,35,16,9,21,7,36,19,31,17,54,10,28,27,47,0,27,41,32,6,51,14,9,31,41,19}

    "abbaabbbabaaaabbaaabababbaabbabbbbaaaabbbaaaaaababaababbaaaaabaaabaaaaabbaabaabaaab"

    "a"

    Returns: 1131

  27. {0,1,2,2,4,3,6,2,7,1,6,11,10,11,8,7,1,12,9,16,4,20,6,7,1,18,5,0,26,27,7,7,1,5}

    "ababababaaabbabbaabbbbbabbaabababa"

    "abababab"

    Returns: 4087988

  28. {0,0,1,2,4,2,3,3,6,3,10,7,11,4,7,5,8,3,5,16,11,20,3,10,8,18,0,11,10,27,15,10,26,0,33,31,4,10,11,2,20,7,30,15,23,18,11,3,16,14,0,9,9,46,36,24,15,14,45,53,42,29,22,52,40,27,16}

    "bcaababbacacbcbbcccacbbbbccbaccaabccababacbcacbaccbbaccabbabaaaabaa"

    "bcbac"

    Returns: 471428136

  29. {0,0,0,2,0,2,2,1,0,6,0,1,1,8,3,2,1,9,0,7,14,3,20,12,0,24,5,6,8,23,23,25,4,30,15,18,29,37,29,29,16,12,24,21,36,10,10,33,29,20,33,21,17,48}

    "ccccdbdcbdadcbbbbcbdcbdbcdacbcabddbaabcbacbabcaacbabac"

    "dcbdbad"

    Returns: 59338636

  30. {0,1,1,0,4,5,2,3,2,3,3,2,8,11,12,4,10,16,14,18,14,8,10,14,6,1,0,27,0,17,5,3,8,24,0,13,0,3,37,8,29,4,20,31,0,0,22,39,18,34,37,30,2,46,54,37,28,46,5,32,48,55,20,45,13,54,3,10,65,21,16,51,45,26,6,75,50,18,16,66,74,39}

    "bbbababbabaabbbabbbababaabbabbaabbbbaaaabbbbbbbaababbaaabbabaaaaabababbbbabbbbabba"

    "b"

    Returns: 286

  31. {0,0,2,3,3,2,1,7,6,4,8,3,3,10,12,3,8,9,12,6,20,14,21,2,9,10,12,1,25,22,7,3,11,29,0}

    "adacabdcbbdacbadcccdcdadcdccbdbcaac"

    "bc"

    Returns: 203308

  32. {0,1,0,1,2,5,6,7,6,5,5,0,3,7,11,12,14,5,3,3,16,7,13,19,0,4,25,24,8,2}

    "acdbadccbacdcbdaaddddcbcbdbadd"

    "bacab"

    Returns: 849739

  33. {0,1,0,0,4,4,1,5,4,5,7,4,6,11,9,11,10,13,8,17,11,18,19,12,11,17,4,13,19,4,11,27,32,33,22,3,30,19,12,14,39,22,19,11,36}

    "baaabababaabbabbababababbaabababbaaabaababbba"

    "bababab"

    Returns: 379265821

  34. {0,1,1,1,2,2,5,4,4,7,5,10,12,8,13,3,8,15,4,10,10,8,20,17,21,16,0,18,1,22,13,5,9,2,30,13,18,3,16,31,14,15,9,24,6,0,42,23,30,38,11,11,43,30,11,22,25,54,44,26,17,17,28,27,37,9,7,53,12,62,60,39,19,9,72,29,54,74,73}

    "acaccabccacabcccaaabcccacabbbaccbbacabcabaacbcabbcbbbbbacbbaccabbcaacaabaabbbcc"

    "bababca"

    Returns: 488820536

  35. {0,0,2,0,0,0,6,5,5,0,8,9,2,3,12,1,13,7,6,10,8,17,11,4,17,5,5,7,4,8,13,28,29,6,7,34,33,37,4,25,38,39,35,10,35,3,27,17,8,49,19,44,6,39,53,37}

    "baabbaaababaaababbbabbaabbaaababbaaaaabaaaababaaabababaa"

    "b"

    Returns: 3211

  36. {0,0,1,3,0,0,2,4,7,0,7,3,5,8,2,10,11,6,0,6,19,10,9,23,1,4,21,17,7,6,2,29,32,20,22,28,22,22,26,3,3,1,24,43,8,44,15,19,33,19,37,28,8,7,0,21,13,31,27,19,53,9,18,50,59,40,29,45,58,14,41,26,37,54,32,1,42,51,16}

    "ccbcccaabacbbaaccabacbcbabbbbbccbbacabccacaacaabbbaabcbaabababaacccaccbccbababb"

    "acacb"

    Returns: 854226635

  37. {0,0,0,3,2,5,3,1,7,9,1,1,10,3,5,0,1,1,18,12,2,12,13,16,17,16,8,19,19,10,7,20,24}

    "aabccccaacbccaabbcccbbccbdacdabdb"

    "b"

    Returns: 617

  38. {0,1,2,1,3,5,0,0,8,5,6,3,4,11,13,11,8,12,9,11,19,20,4,19,17,12,1,19,8,17,1,16,1,10,6,33,18,17,18,20,32,20,16,6,29,12,3,40,30,6,39,48,35,51,37,23,33,15,41,48,31,59,16,17,52,49,20,45,27,1,19,10,68,5,49,75,39,72,41,24,52,29,49,81,1,51,83,72,80,19}

    "cbacaccaaabcbbabacbaaaacbcbbaaaababbbabcccaccbbbcbcbcabbcbbabaccbaccccacbabbbbccbbabcbbcab"

    "ac"

    Returns: 17852

  39. {0,0,0,1,2,0,6,6,1,3,9,8,8,7,1,2,2,16,6,1,2,4,16,8,9,7,10,14,10,18,26,7,24,12,12,33,34,14,19,16,25,28,39,43,10,33,6,9,8,17,3,44,41,0,10,21,24,0,37}

    "babbabbbbbbbaaababaaaabaabaaaababbabaababaaabaabaabbbbabbaa"

    "a"

    Returns: 2735

  40. {0,0,2,2,1,2,2,6,8,4,7,9,6,12,10,14,6,12,11,18,12,7,17,17,4,11,24,26,8,21,9,7,22,11,18,5,8,17,8,10,23,5,4,40,20,13,46,41,12,21,33,35,28,28,39,46,53,16,25,59,45,6,25,8,28,2,14,45}

    "bbbbbbaabbbbabbbaabbabbabbabbbbabbbbbabaabbabbabbabbbbabababaabbaaab"

    "ab"

    Returns: 1199

  41. {0,1,0,3,2,3,1,7,0,0,3,0,1,7,2,10,9,9,0,0,9,6,22,20,17,22,7,8,21,14,19,6,0,12,34,22,32,32,12,15,2,9,30,19,29,28,18,0,5,20,1,7,3,47,33,30,5,13,54,40,31,4,4,19,36,38,10,3,62,48,0,61,4,58,19}

    "bccabababcbbccabbbcccacbcccacccbbaacabacbcabbacccccbbccaccccacbabbaabaaccac"

    "cbcacba"

    Returns: 298986156

  42. {0,1,0,3,4,4,5,2,6,4,2,2,10,10,6,15,16,4,9,13,11,19,11,21,12,25,3,17,2,19,18,19,9,8,30,28,32,20,16,11,37,1,25,20,42,24,37,37,22,46,38,16,40,44,18,29,22,57,38,58,46,0,24,1,17,42,4,28,31,41,10,12,51,7,15,38,13,65,75,61,61,29,80,38,53,4,5,64,22,41,36}

    "bcbdadaadcaaaabbccaadacadbcbabbdacbacdaaacccbdbacbbcdcdbdcccdaaaddaccbaabbcabdaaacbdacabccd"

    "cdac"

    Returns: 369680315

  43. {0,1,0,1,2,0,4,7,3,7,5,9,4,12,9,0,11,13,13,6,0,3,7,21,9,17,22,12,8,10,5,21,3,22,19,14,28,34,11,17,39,7,35,5,35,23,12,15,45,26,9,0,4,12,25,9,0,54,38,1,9,20,36,14,25,51,38,63}

    "acbbcbbacbbaccacbbcabbccbcbacbbbabbcaaacabccbcbccabcacacbacacccbaacb"

    "acbac"

    Returns: 431925540

  44. {0,1,0,2,1,4,5,4,0,8,7,6,2,1,9,15,10,7,14,14,18,0,21,7,16,7,10,16,2,26,16,6,22,21,33,28,36,17,21,26,31,4,13,6,24,14,6,39,28,23,36,31,5,23,8,51,16,9,31}

    "bcaabbbbaccacacacabcacabcacbbcccbaacacabcbbabababacababbbcb"

    "cbacbab"

    Returns: 792433761

  45. {0,0,1,2,0,2,0,6,3,2,7,4,8,11,1,10,5,5,11,8,15,12,5,21,11,3,9,18,9,11,15,15,20,26,27,23,20}

    "ccacbccacbacabcbbbabaccabbcccaaababba"

    "cbca"

    Returns: 5292790

  46. {0,1,0,2,3,4,4,6,5,3,6,1,4,9,14,9,4,7,1,15,0,12,13,16,11,13,4,12,21,26,20,6,10,10,16,10,0,3,0,3,11,30,14,33,32,39,25,33,47}

    "gienatjzwxclkkulncaqptoneqlnbtoddbmivazxzmcojdhis"

    "kaxiagt"

    Returns: 223838992

  47. {0,1,2,3,2,3,3,0,5,8,8,6,8,11,7,5,9,3,16,11,10,2,9,8,11,3,16,0,10,5,13,14,16,18,2,15,12,18,32,23,8,41,34,20,10,2,6,9,32,38,29,20,14,40,41,3,13,5,51,19,48}

    "babbaaababbabaaababbbaaaabaaabababbaaabbbabaaabaaaababbbabbba"

    "babababa"

    Returns: 394435662

  48. {0,1,2,3,2,4,2,0,6,8,8,7,6,7,10,14,8,15,3,19,3,19,2,21,6,4,22,13,0,13,1,8,11,23,9,10,20,1,35,4,32,33,36,28,4,23,1,29,31,27,19,19,18,43,38,40,8,30,18,21,51}

    "dbcdccaccbaacaaabbbbdabaadaacacabcddddbacbbadaaababbbaadccaca"

    "adbdcadc"

    Returns: 757466845

  49. {0,1,0,1,4,3,4,1,3,3,0,10,2,6,12,12,13,2,11,7,8,14,20,2,16,21,26,6,1,11,0,29,17,13,0,6,33,34,0,4,10,36,33,3,28,6,14,35,41,17,40,24,46,39,19,32,28,21,39,35,60,41,17,56,32,18,64,41,46,61,28,32,21,31,26,11,37,53,57,5,6,76,1,78,20,48,29,13,38,2,28,83,82,74}

    "bdcdbadcadddbbbbbdcbaacabdcbdcdabcccaaaddddcddbdabbdaaaddddcdacbbbcadbcddbcaadbddcbdbaacdbcacb"

    "abdad"

    Returns: 378838769

  50. {0,1,2,3,4,4,5,7,0,2,4,1,5,3,0,4,13,1,18,10,15,10,18,4,10,10,14,15,5,7,3,21,32,0,4,18,32,0,31,33,32,11,40,42,20,11,11,6,36,44,35,5,40,38,15,54,30,42,46,39,4,0,16,23,57,44,19,54,49,65,37,4,21,30,40,13,8,35,62,26,2,23,3}

    "babbababaaaaaabaabaaabbbabbaabbbaababbaaabbabbaaababababbbbbabbbaaaaabbbbbabbbbaaab"

    "bab"

    Returns: 86679702

  51. {0,0,0,1,2,2,4,6,2,8,6,8,2,13,6,4,2,10,11,8,12,7,4,15,10,5,23,17,26,6,0,7,2,18,19,26,36,33,7,10,40,30,16,40,33,21,44,39,13,22,3,31,34,28,54,19,26,15,33,1,5,45}

    "baabbbbbbbabbaaaabbbabaaabaabaaaaaaabbaababbaababbaaabbaabbabb"

    "ba"

    Returns: 862

  52. {0,1,0,2,1,2,6,6,3,7,3,0,10,7,1,0,5,14,18,6,12,8,3,5,10,9,5,14,27,16,30,23,5,4,30,23,23,20,3,29,7,29,18,25,38,4,9,18,35}

    "abbbbbbaacabccccbcbccabbcaccaaacaaccaacbaccacbcac"

    "ba"

    Returns: 45730

  53. {0,0,2,0,3,2,4,4,2,1,3,5,3,3,3,11,15,15,0,8,9,12,5,22,13,3,23,17,3,27,4,21,17,19,16,9,27,34,2,29,14,39,41,17,27,0,45,23,28,32,22,29,19,11,15,14,11,34,57,23,26,41,44,52,18}

    "cdbaabcadacaccdbdbbddccabdaaacbabddabbcbdcddaacaccdcdcbbccdddcddd"

    "aba"

    Returns: 377210925

  54. {0,1,1,0,0,0,4,0,5,9,4,1,2,13,2,11,5,6,9,6,8,11,16,14,7,5,5,16,12,28,0,19,13,31,11,13,18,12,9,23,14,2,19,34,42,24,21,28,19,11,31,27,28,18,11,23,1,9,54,10,9,15,35,3,29,58,63,27,54,41,34,20,70,42,7,63,12,37,46,5,40,59,69,80,29,43,16,43}

    "ibvpszznopfgaxzgfltlsxbtumilocltgcozgtziufuzimxeekwnysbicrfxdiogcseozpscrhjotyczcwmbaaol"

    "vub"

    Returns: 561544161

  55. {0,1,0,0,0,3,5,5,0,2,0,7,0,6,9,2,12,3,0,8,2,2,6,22,23,19,24,0,25,12,17,22}

    "cdbccdbbbdaabbcadaabadccaccbacca"

    "acbc"

    Returns: 3967414

  56. {0,0,1,2,1,2,2,5,0,9,6,6,1,13,13,6,7,11,16,4,19,8,8,11,21,16,24,18,14,13,10,6,12,27,1,27,35,25,14,4,8,27,15,12,43,44,37,8,33,7,37,45,51,46,13}

    "bdadaabbdbadcdaacbaabbcabdcbdbddbcbdcbacabacbdbdcdbdcda"

    "dadaca"

    Returns: 793592397

  57. {0,1,2,2,0,4,5,1,4,4,1,8,4,9,10,12,16,12,17,12,9,8,14,9,8,8,0,16,24,3,28,24,24,31,25,29,7,12,37}

    "bccaaabacbabbaabaabcccaacbabcbaaaababaa"

    "bacbcaca"

    Returns: 79014533

  58. {0,0,2,3,3,1,2,0,7,3,5,5,3,6,11,6,4,5,11,8,2,7,9,7,6,15,9,5,2,23,7,4,13,2,16,32,7,1,28,17,8,18,23,12,27,13,7,39,1,24,7,10,32,36,49,3,25,51,8,1,36,21}

    "abbabbabbbbaabbbbaaaaaaabaabbabbabbbaababbbbbbaaaaaabababbabbb"

    "abababab"

    Returns: 112647143

  59. {0,1,1,3,2,0,1,1,3,1,0,7,6,6,1,0,1,11,13,17,18,16,18,13,4,10,26,20,10,23,6,15,19,10,25,17,26,10,8,33,9,34,11,10,37,16,42,19,10,41,2,16,29,10,37,0,24,51,45,10,13,29,58,9,10,54,1,19,26,11,11,9,38,56,11,43,19,6,13,64,78,32,82,47,50,26,13,17,49,25,5,13,9,20,82,35,67,10,21,57}

    "acaabcaacbccbccbabbabaaacccaacbcacbabcbbabbacbbacacabaabaabaaccacabaaacacbbcaccbcccccbbacaabbbbacbab"

    "ababcaca"

    Returns: 681985684

  60. {0,1,0,2,2,2,1,0,2,6,0,9,9,8,7,10,15,16,5,16,5,3,12,13,5,4,5,7,23,0,29,20,4,17,21,34,0,13,36,35,18,7,16,20,7,7,30,32,24,35,32,27,0,25,42,28,17,29,34,22,55,4,8,62,19,57,50,14,27,9,42,56,15,73,10,62,37,29,48,64,70,73,51,31,71,23,7,25,39,59,64,12,28,64,34,87,94,94,39,31}

    "babacbacacabacbbaabaacbbccbbccbacbacaaaacbbbbacbabcaccaaacabbcabcbbbcccbbaccbcaccacabbcaccbccbaabcab"

    "acbababc"

    Returns: 305983965

  61. {0,0,2,0,4,5,0,7,8,9,0,11,12,13,14,0,16,17,18,19,20,0,22,23,24,25,26,27,0,0,30,0,32,33,0,35,36,37,0,39,40,41,42,0,44,45,46,47,48,0,50,51,52,53,54,55,0,0,58,0,60,61,0,63,64,65,0,67,68,69,70,0,72,73,74,75,76,0,0,79,0,81,82,0,84,85,86,0,88,89,90,91,0,93,94,95,96,97}

    "abacbadcbaedcbafedcbagfedcbahghfghefghdefghcdefghbcdefghabacbadcbaedcbafedcbahghfghefghdefghcdefgh"

    "abcdefgh"

    Returns: 857843949

  62. {0,0,1,1,4,1,6,7,1,9,10,11,1,13,14,15,16,1,18,19,20,21,22,1,24,25,26,27,28,29,1,1,32,1,34,35,1,37,38,39,1,41,42,43,44,1,46,47,48,49,50,1,52,53,54,55,56,57,1,1,60,61,1,63,64,65,66,1,68,69,70,71,72,73,1,75,76,77,1,79,80,81,82,83,1,85,86,87,88,89,90,91}

    "aababcabacabdacabadacabeadacabaeaaeadaeaadaeacadaeaacadaeabcabdacabeadacabdaeacadaeabacadaea"

    "bacadaea"

    Returns: 199608798

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: