message: Update rotate-string.cpp
diff: -// Time: O(n + m)
  +// Time: O(n )
  // Space: O(1)
  // Rabin-Karp Algorithm (rolling hash)
  class Solution {
  public:
  bool rotateString(string A, string B) {
  + if (A.length() != B.length()) {
  + return false;
  + }
  static const uint64_t M = 1000000007;
  static const uint64_t p = 113;
  static const uint64_t p_inv = pow(p, M - 2, M);
  - const auto q = (B.length() + A.length() - 1) / A.length();
  -
  uint64_t b_hash = 0, power = 1;
  for (int i = 0; i < B.length(); ++i) {
  b_hash += power * B[i];
  @@ -29,7 +30,7 @@ public:
  }
  power = (power * p_inv) % M;
  - for (int i = B.length(); i < (q + 1) * A.length(); ++i) {
  + for (int i = B.length(); i < 2 * A.length(); ++i) {
  a_hash -= A[(i - B.length()) % A.length()];
  a_hash *= p_inv;
  a_hash += power * A[i % A.length()];
  @@ -65,9 +66,63 @@ private:
  }
  };
  -// Time: O(n * m)
  +// Time: O(n)
  // Space: O(n)
  +// KMP algorithm
  class Solution2 {
  +public:
  + bool rotateString(string A, string B) {
  + if (A.length() != B.length()) {
  + return false;
  + }
  + return strStr(A + A, B) != -1;
  + }
  +
  +private:
  + int strStr(string haystack, string needle) {
  + if (needle.empty()) {
  + return 0;
  + }
  +
  + return KMP(haystack, needle);
  + }
  +
  + int KMP(const string& text, const string& pattern) {
  + const vector<int> prefix = getPrefix(pattern);
  + int j = -1;
  + for (int i = 0; i < text.length(); ++i) {
  + while (j > -1 && pattern[j + 1] != text[i]) {
  + j = prefix[j];
  + }
  + if (pattern[j + 1] == text[i]) {
  + ++j;
  + }
  + if (j == pattern.length() - 1) {
  + return i - j;
  + }
  + }
  + return -1;
  + }
  +
  + vector<int> getPrefix(const string& pattern) {
  + vector<int> prefix(pattern.length(), -1);
  + int j = -1;
  + for (int i = 1; i < pattern.length(); ++i) {
  + while (j > -1 && pattern[j + 1] != pattern[i]) {
  + j = prefix[j];
  + }
  + if (pattern[j + 1] == pattern[i]) {
  + ++j;
  + }
  + prefix[i] = j;
  + }
  + return prefix;
  + }
  +};
  +
  +// Time: O(n^2)
  +// Space: O(n)
  +class Solution3 {
  public:
  bool rotateString(string A, string B) {
  return A.size() == B.size() && (A + A).find(B) != string::npos;
  