Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目

幾種配對其中一個字串是另一個字串的前綴+後綴



思路

用Rolling Hash來配對


```cpp

class RollingHash {
    long long mod, base;
    vector<long long> h, p;
public:
    template<class T>
    RollingHash(){}
    template<class T>
    RollingHash(const T& data, long long mod, long long base): mod(mod), base(ba
se), h{0}, p{1} {
        for(auto& d: data) {
            h.push_back((h.back() * base + d) % mod);
            p.push_back(p.back() * base % mod);
        }
    }
    long long hash(int l, int r) {
        return (h[r+1] - h[l] * p[r-l+1] % mod + mod) % mod;
    }
};


class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words)
    {
        int n = words.size();
        vector<RollingHash> rhs;
        for(int i = 0 ; i < n ; i ++)
        {
            RollingHash rh(words[i],1e9+7,931104);
            rhs.push_back(rh);
        }

        int res = 0 ;

        for(int i = 0 ; i < n ; i ++)
        {
            int len1 = words[i].size();
            for(int j = i+1 ; j < n ; j ++)
            {
                int len2 = words[j].size();

                if(len1>len2)continue;

                if( rhs[j].hash(0,len1-1) == rhs[i].hash(0,len1-1) && rhs[j].has
h(len2-len1,len2-1) == rhs[i].hash(0,len1-1) )res ++;
            }
        }

        return res;
    }
};```






--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.169.39 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736315992.A.883.html
推 Meaverzt: 大師
→ Meaverzt: 剩我只會暴力解了