# 466. Count The Repetitions¶

• Time: $O(|\texttt{s1}||\texttt{s2}|)$
• Space: $O(|\texttt{s2}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 struct Record { int count; int nextIndex; Record(int count, int nextIndex) : count(count), nextIndex(nextIndex) {} }; class Solution { public: int getMaxRepetitions(string s1, int n1, string s2, int n2) { // [count(s1 matches s2[i..n)), next index of s2[i..n)] vector records; for (int i = 0; i < s2.length(); ++i) { int count = 0; int nextIndex = i; for (int j = 0; j < s1.length(); ++j) if (s2[nextIndex] == s1[j]) if (++nextIndex == s2.length()) { // There's a match. ++count; nextIndex = 0; } records.emplace_back(count, nextIndex); } int matches = 0; // s1 matches s2. int index = 0; while (n1--) { matches += records[index].count; index = records[index].nextIndex; } return matches / n2; // s1 matches s2. } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Record { public int count; public int nextIndex; public Record(int count, int nextIndex) { this.count = count; this.nextIndex = nextIndex; } }; class Solution { public int getMaxRepetitions(String s1, int n1, String s2, int n2) { // [count(s1 matches s2[i..n)), next index of s2[i..n)] List records = new ArrayList<>(); for (int i = 0; i < s2.length(); ++i) { int count = 0; int nextIndex = i; for (int j = 0; j < s1.length(); ++j) if (s2.charAt(nextIndex) == s1.charAt(j)) if (++nextIndex == s2.length()) { // There's a match. ++count; nextIndex = 0; } records.add(new Record(count, nextIndex)); } int matches = 0; // s1 matches s2. int index = 0; while (n1-- > 0) { matches += records.get(index).count; index = records.get(index).nextIndex; } return matches / n2; // s1 matches s2. } }