I'm learning C++ and trying to solve a problem where I need to determine how many rotations of string S can match string T. Here's my current code:
```cpp
#include
using namespace std;
int main(){
int n; // Length of string
string S, T;
cin >> n;
cin.ignore();
cin >> S; // Input for S
cin.ignore();
cin >> T; // Input for T
int check = 0;
while(1){
char s_sub = S[0]; // Store the first element in every iteration
for(int i = 1; i <= n - 1; i++){
S[i - 1] = S[i]; // Shift elements by 1 position to left
}
S[n - 1] = s_sub;
check++;
if(S == T){ // Will break if strings become equal
break;
}
}
cout << check;
return 0;
}
```
I feel like there must be a better way to handle the time complexity without rotating the string every time. Any suggestions would be appreciated!
3 Answers
Another way to speed this up is to avoid manual input from users during testing! Just hard-code your test cases to save time, since the rotation calculations are much faster than user input!
Your method could be further optimized by not actually rotating the string. Instead, you only need to check if characters match at specific positions after finding where S[0] occurs in T. Use a helper function for the comparison to keep your code organized and efficient. Start checking from the first occurrence of S[0] in T, and wrap around as necessary!
It looks like your code can be improved! Instead of rotating the string in each iteration, you could concatenate S to itself and check if T is a substring of this new string. If T is a rotation of S, it will definitely be a substring of S + S. Here’s a simple way to implement that:
```cpp
string doubled = S + S;
size_t pos = doubled.find(T);
if (pos != string::npos && pos < S.size())
cout << pos;
else
cout << -1;
```
This approach reduces unnecessary character shifts and should yield better performance!
Thanks! I like this idea but when I tried it, it failed in some test cases. Maybe I'm missing something?
That sounds interesting! I'll give that a shot and see if it works.