1
class Solution {
2
 public:
3
  string shortestPalindrome(string s) {
4
    int BASE = 26, MOD = 1e9 + 7;
5
    int start = s.size() - 1;
6

7
    // Calculate hash values from front and back
8
    long front = 0, back = 0;
9
    long power = 1;
10

11
    for (int i = 0; i < s.size(); i++) {
12
      front = (front * BASE + (s[i] - 'a' + 1)) % MOD;
13
      back = (back * BASE + (s[start--] - 'a' + 1)) % MOD;
14
      power = (power * BASE) % MOD;
15
    }
16

17
    // If hash values of both front and back are same, then it is a palindrome
18
    if (front == back) {
19
      return s;
20
    }
21

22
    // As it is not palindrome, add last characters in the beginning, and then
23
    // check. Store the hash value of the newly added characters from front and
24
    // back
25

26
    // new_front will be added to front to get new hash value
27
    // new_back will be added to back to get new hash value
28
    long new_front = 0, new_back = 0;
29
    long new_power = 1;
30

31
    int end = s.size() - 1;
32
    string ans = "";
33

34
    while (end >= 0) {
35
      // Taking character from ending
36
      int ch = (s[end] - 'a' + 1);
37

38
      new_front = (new_front * BASE + ch * power) % MOD;
39
      new_back = (ch * new_power + new_back) % MOD;
40
      new_power = (new_power * BASE) % MOD;
41

42
      int final_front = (new_front + front) % MOD;
43
      back = (back * BASE) % MOD;
44
      int final_back = (new_back + back) % MOD;
45

46
      // Storing it in separate string
47
      ans += s[end];
48
      end--;
49

50
      // Both hashes are same
51
      if (final_front == final_back) {
52
        break;
53
      }
54
    }
55
    return ans + s;
56
  }
57
};