首页 > 其他 > 详细

LC 1316. Distinct Echo Substrings

时间:2020-05-10 10:03:57      阅读:44      评论:0      收藏:0      [点我收藏+]

link

技术分享图片

 

class Solution {
public:
    long mod = 100000000000007L;
    long head=1L;
    int distinctEchoSubstrings(string text) {
        int n=text.size();
        
        unordered_set<long> st;
        for(int l=1;l<=n/2;++l){
            head*=26L;
            head%=mod;
            int leftidx=0;
            int rightidx=l;
            long leftHash=initHash(text,0,l);
            long rightHash=initHash(text,l,l);
            if(leftHash==rightHash) st.insert(leftHash);
            
            leftidx++;
            rightidx++;
            while(rightidx+l<=n){
                leftHash=reHash(leftHash,text,leftidx-1,leftidx+l-1);
                rightHash=reHash(rightHash,text,rightidx-1,rightidx+l-1);
                if(leftHash==rightHash) st.insert(leftHash);
                ++leftidx,++rightidx;
            }
        }
        return st.size();
    }
    
    long initHash(string& text, int idx, int len){
        long hash=0;
        for(int i=idx;i-idx+1<=len;++i){
            hash=((hash*26L)%mod+text[i]-a+1)%mod;
        }
        return hash;
    }
    
    long reHash(long hash, string& text, int idx1, int idx2){
        int add=text[idx2]-a+1;
        int sub=text[idx1]-a+1;
        hash=((hash*26L)%mod+add)%mod;
        hash=(hash-head*sub)%mod;
        hash=(hash+mod)%mod;
        return hash;
    }
};

 

LC 1316. Distinct Echo Substrings

原文:https://www.cnblogs.com/FEIIEF/p/12862173.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!