1163. Last Substring in Lexicographical Order, C++ (gcc)

1163. Last Substring in Lexicographical Order

const int P = 37;
const int mod = 1e9+7;

typedef long long int ll;

ll fast_pow (ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    
    return ans;
}

ll divide (ll numerator, ll denominator) {
    return (numerator * fast_pow (denominator, mod-2)) % mod;
}

struct Hashing {
    private: 
    
    const string& s;
    vector<ll> prefixHash;
    vector<ll> powerP, invPower;
    
    void buildInitialHash() {
        int length = s.length();
        prefixHash = powerP = invPower = vector<ll>(length+1);
        
        powerP[0] = invPower[0] = 1;
        // p^i = p^(i-1) * p
        for (int j = 1; j <= length; j ++) {
            powerP[j] = (powerP[j-1] * P) % mod;
            invPower[j] = divide (1, powerP[j]);
        }
        
        for (int j = 1; j <= length; j ++) {
            int currentChar = s[j-1];
            prefixHash[j] = (prefixHash[j-1] + (powerP[j] * currentChar)) % mod;
        }
    }
    
    public: 
    ll getHash (int l, int r) {
        l ++, r ++;
        ll currentHash = (prefixHash[r] - prefixHash[l-1] + mod) % mod;
        return (currentHash * invPower[l-1]) % mod;
    }
    
    bool isSame (int l1, int r1, int l2, int r2) {
        return (getHash(l1, r1) == getHash(l2, r2));
    }
    
    Hashing (const string& _s) : s(_s) {
        buildInitialHash();
    }
};

class Solution {
    
    bool isFirstLarger (int pos1, int pos2, const int length, Hashing& hasher, const string& s) {
        int maxPossibleLength = min (length - pos1, length - pos2);
        int l = 0, r = maxPossibleLength;
        
        while (l < r) {
            int m = (l+r) >> 1;
            if (hasher.isSame (pos1, pos1+m, pos2, pos2+m)) l = m+1;
            else r = m;
        }
        
        pos1 += l;
        pos2 += l;
        
        if (pos2 == length) return true;
        return (s[pos1] > s[pos2]);
    }
    
public:
    string lastSubstring(string s) {
        Hashing hasher (s);
        
        int length = s.length();
        
        char largestChar = (char)(0);
        for (char ch : s) largestChar = max(largestChar, ch);
        
        vector<int> largestCharPositions;
        for (int i = 0; i < length; i ++) {
            if (largestChar != s[i]) continue;
            
            largestCharPositions.push_back(i);
        }
        
        int result = largestCharPositions[0];
        
        for (int i = 1; i < largestCharPositions.size(); i ++) {
            if (!isFirstLarger (result, largestCharPositions[i], length, hasher, s)) {
                result = largestCharPositions[i];
            }
        }
        
        return s.substr(result);
    }
};


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development