A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 686. Repeated String Match, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
The notes already sitting in the source point us in the right direction:
- failed
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are repeatedStringMatch, power, gcd, modInverse, check.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//failed
02class Solution {
03public:
04 int repeatedStringMatch(string A, string B) {
05// if(A.find(B) != string::npos){
06// /**
07// A: "aa"
08// B: "a"
09// **/
10// return 1;
11// }
12// int prev_s = 0, s = 0;
13// int count = 0;
14
15// while((s = B.find(A, prev_s)) != string::npos){
16// cout << "prev_s: " << prev_s << ", s: " << s << endl;
17// if(prev_s == 0){
18// //the first occurent of A in B should at 0 ~ A.size()-1
19// if(s >= A.size()) return -1;
20// //B[0:s] should be a substring of A
21// if(A.find(B.substr(0, s)) == string::npos){
22// return -1;
23// }else if(s != 0){
24// count++;
25// }
26// count++;
27// cout << "first" << endl;
28// // }else if(s + A.size()*2 > B.size()){
29// // //last occurence
30// // //the last part of B should be a substring of A
31// // if(A.find(B.substr(s+A.size(), A.size())) == string::npos) return -1;
32// // count++;
33// // cout << "last" << endl;
34// }else{
35// //middle occurence
36// //the 's' should be the same as the guessed 'prev_s'
37// if(prev_s != s) return -1;
38// count++;
39// // cout << "middle" << endl;
40// }
41// cout << "count: " << count << endl;
42// //update pointer
43// //guess that the next occurence of A is at (s + A.size())
44// prev_s = s + A.size();
45// }
46
47// cout << "prev_s: " << prev_s << ", s: " << s << endl;
48// if(prev_s == 0){
49// /**
50// A: "abcd"
51// B: "cda"
52// **/
53// //not found any A in B
54// cout << "prev_s== 0" << endl;
55// cout << A.substr(0, 1) << endl;
56// if((s = B.find(A.substr(0, 1))) != string::npos){
57// cout << B.substr(s, A.size()) << endl;
58// if(A.find(B.substr(s, A.size())) != string::npos){
59// count++;
60// }
61// }
62
63// string sub_B = (s != string::npos)?B.substr(0, s):B;
64// cout << sub_B << endl;
65// if(A.find(sub_B) != string::npos){
66// count++;
67// }
68
69// return count;
70// }
71// //if the last occurence of A in B is intact,
72// // then prev_s should be equal to B.size()
73// if(prev_s != B.size()){
74// // prev_s-1+A.size()
75// //last occurence
76// //the last part of B should be a substring of A
77// if(A.find(B.substr(prev_s, A.size())) == string::npos) return -1;
78// count++;
79// cout << "last" << endl;
80// cout << "count: " << count << endl;
81// }
82
83 // int count = 1;
84 // string dup_A = A;
85 // while(dup_A.find(B) == string::npos && dup_A.size() <= B.size()*2){
86 // dup_A += A;
87 // count++;
88 // }
89 // if(dup_A.size() > B.size()*2) return -1;
90 // return count;
91 }
92};
93
94//Approach #1: Ad-Hoc [Accepted]
95//Runtime: 16 ms, faster than 85.90% of C++ online submissions for Repeated String Match.
96//Memory Usage: 9.1 MB, less than 82.08% of C++ online submissions for Repeated String Match.
97//time: O(N * (M+N)), M, N is the length of A and B respectively. M+N is the length of dup_A.
98// We compare dup_A with B, so the time used is the product of their lengths.
99//space: O(M+N), used by dup_A
100class Solution {
101public:
102 int repeatedStringMatch(string A, string B) {
103 string dup_A = A;
104 for(; dup_A.size() < B.size(); dup_A += A){}
105 if(dup_A.find(B) != string::npos) return dup_A.size()/A.size();
106 dup_A += A;
107 if(dup_A.find(B) != string::npos) return dup_A.size()/A.size();
108 return -1;
109 }
110};
111
112//Approach #2: Rabin-Karp (Rolling Hash) [Accepted]
113//Runtime: 8 ms, faster than 97.22% of C++ online submissions for Repeated String Match.
114//Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for Repeated String Match.
115//time: O(M+N), space: O(1)
116class Solution {
117public:
118 // To compute x^y under modulo m
119 int power(int x, unsigned int y, unsigned int m){
120 if (y == 0)
121 return 1;
122 long long p = power(x, y/2, m) % m;
123 p = (p * p) % m;
124
125 return (y%2 == 0)? p : (x * p) % m;
126 };
127
128 // Function to return gcd of a and b
129 int gcd(int a, int b){
130 if (a == 0)
131 return b;
132 return gcd(b%a, a);
133 };
134
135 // Function to find modular inverse of a under modulo m
136 // Assumption: m is prime
137 int modInverse(int a, int m){
138 int g = gcd(a, m);
139 if (g != 1){
140 return -1;
141 }else{
142 // If a and m are relatively prime, then modulo inverse
143 // is a^(m-2) mode m
144 return power(a, m-2, m);
145 }
146 };
147
148 bool check(int index, string A, string B){
149 for(int i = 0; i < B.size(); i++) {
150 if(A[(i+index) % A.size()] != B[i]){
151 return false;
152 }
153 }
154 return true;
155 }
156 int repeatedStringMatch(string A, string B) {
157 /*
158 the expanded A's length should be >= B's length
159 A.size() * q = B.size() + A.size() -1,
160 which is just larger than B.size(),
161 because (B.size() + A.size() -1) - A.size() =
162 B.size() - 1, this is smaller than B.size()
163 */
164 int q = (B.size() - 1)/A.size() + 1;
165 //p: just a prime number
166 int p = 113, MOD = 1000000007;
167 int pInv = modInverse(p, MOD);
168
169 /*
170 hash(S) = p^0 * S[0] + p^1 * S[1] + ... + p^(n-1) * S[n-1]
171 */
172 long long bHash = 0, power = 1;
173 for(int i = 0; i < B.size(); i++){
174 bHash += power * int(B[i]);
175 bHash %= MOD;
176 power = (power * p) % MOD;
177 }
178
179 /*
180 first expand string A to B.size()
181 aHash: the hash of expanded string A
182 */
183 long long aHash = 0;
184 power = 1;
185 for(int i = 0; i < B.size(); i++){
186 aHash += power * int(A[i % A.size()]);
187 aHash %= MOD;
188 power = (power * p) % MOD;
189 }
190
191 //now power = p^(n-1) % MOD
192
193 if(aHash == bHash && check(0, A, B)) return q;
194 power = (power * pInv) % MOD;
195 //now power = p^(n-2) % MOD = p^(-1) % MOD(by Fermat's Little Theorem)
196
197 for(int i = B.size(); i < (q + 1) * A.size(); i++){
198 /*
199 in each iteration, pop a char from front and append a char to tail
200 the (string represented by aHash)'s size remains B.size()
201
202 S: the expanded string A
203 x: the char to be appended
204 n: the size of the expanded string A, here it's B.size()
205 p: the prime number
206 hash(S[1:] + x) = [hash(S) - S[0]]/p + p^(n-1)*x
207 */
208 //-S[0]
209 aHash -= int(A[(i - B.size()) % A.size()]);
210 //divided by p
211 aHash *= pInv;
212 //power: p^(n-1)
213 //A[i % A.size()]: the appended char
214 aHash += power * int(A[i % A.size()]);
215 aHash %= MOD;
216 /*
217 i - B.size() + 1: the first char in current string
218 represented by aHash is A[(i - B.size() + 1)%A.size()]
219 */
220 if(aHash == bHash && check(i - B.size() + 1, A, B)){
221 return i < q * A.size() ? q : q+1;
222 }
223 }
224 return -1;
225 }
226};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.