(review) leetcode 2156. find substring with given hash value (weekly contest 278)

5825 ワード
leetcode テキストリンク
https://leetcode.com/contest/weekly-contest-278/problems/find-substring-with-given-hash-value/
1st try: time limit exceed
2nd try: time limit exceed (pre computing)
3rd try: pass (pre computing more)
class Solution:
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        xa = [1+ord(ch)-ord('a') for ch in s]
        xb = [1] * (k+1)
        for i in range(1, k+1):
            xb[i] = (xb[i-1] * power) % modulo
        n = len(xa)
        h = sum(xa[n-k+i]*xb[i] for i in range(k))
        r = n-k
        for i in range(n-k-1, -1, -1):
            h = (h*power + xa[i] - xa[i+k]*xb[k]) % modulo
            if h == hashValue:
                r = i
        return s[r:r+k]
java.lang.ArrayIndexOutOfBoundsException: length=1; index=1
ログトレース.NETフレームワーク