466. Count The Repetitions

• 466. Count The Repetitions
  • Description
  • Intuition
  • Solution
    • Explanation for Adding Up
  • Reference

Description

link

这道题理解的时候，在它define obtain的时候，举了一个例子，用了 s1 和 s2, 结果后面题目又说了s2 can be obtained from s1, 其实define obtain的时候只是随便举个例子，s1和s2与参数s1和s2毫无关系。

Intuition

首先，初步观察可得：

If s2 repeats in S1 R times, then S2 must repeats in S1 R / n2 times.

Solution

    final int[] repeatCount = new int[s2.length() + 1], nextIndex = new int[s2.length() + 1];
    int j = 0, rep = 0;
    for (int k = 1; k <= n1; k++) {
      for (int i = 0; i < s1.length(); i++) {
        if (s1.charAt(i) == s2.charAt(j)) {
          j++;
          if (j == s2.length()) {
            j = 0;
            rep++;
          }
        }
      }
      repeatCount[k] = rep;
      nextIndex[k] = j;
      for (int start = 0; start < k; start++) {
        if (nextIndex[start] == j) { // used as a set.
          int beforePattern = repeatCount[start];
          int patternCount = (repeatCount[k] - repeatCount[start]) * ((n1 - start) / (k - start));
          int afterPattern = repeatCount[start + (n1 - start) % (k - start)] - repeatCount[start];
          return (beforePattern + patternCount + afterPattern) / n2;
        }
      }
    }
    return rep / n2;

这里的 nextIndex[k] 只是代表了这回 s2 iterate 到了 nextIndex[k] (exclusive)

• beforePattern

  • s1 = "bacaba" , s2 = "abacab", n1 = 3, n2 = 1
    • nextIndex = [0, 3, 1, 1, 0, 0, 0]
    • repeatCount = [0, 0, 1, 2, 0, 0, 0]

• afterPattern

  • s1 = "aaa", s2 = "aa", n1 = 3, n2 = 1
    • nextIndex = [0, 1, 3]
    • repeatCount = [0, 1, 0]

Explanation for Adding Up

• int beforePattern = repeatCount[start];
  • like the example above, it add the repeat time before the patten happens
• int patternCount = (repeatCount[k] - repeatCount[start]) * ((n1 - start) / (k - start));
• int afterPattern = repeatCount[start + (n1 - start) % (k - start)] - repeatCount[start];
  • (n1 - start) % (k - start) 表示完成了所有完整的pattern后，还需要步进多少

Reference

C++ solution inspired by @70664914 with organized explanation