class Rolling_Hash(): def __init__(self,S,base,mod): self.mod=mod self.base=base self.string=S self.power=power=[1]*(len(S)+1) L=len(S) self.hash=h=[0]*(L+1) v=0 for i in range(L): #h[i+1]=v=(v*base+ord(S[i]))%mod h[i+1]=v=(v*base+S[i])%mod v=1 for i in range(L): power[i+1]=v=(v*base)%mod def __hasher(self, X): assert len(X)<=len(self) h=0 for i in range(len(X)): h=(h*self.base+X[i])%self.mod return h def get(self,l,r): return (self.hash[r]-self.hash[l]*self.power[r-l])%self.mod def count(self,T,start=0): alpha=self.__hasher(T) K=0 for i in range(start,len(self)-len(T)+1): if alpha==self[i:i+len(T)]: K+=1 return K def find(self,T,start=0): alpha=self.__hasher(T) for i in range(start,len(self)-len(T)+1): if alpha==self[i:i+len(T)]: return i return -1 def rfind(self,T,start=0): alpha=self.__hasher(T) for i in range(len(self)-len(T),start-1,-1): if alpha==self[i:i+len(T)]: return i return -1 def index(self,T,start=0): alpha=self.__hasher(T) for i in range(start,len(self)-len(T)+1): if alpha==self[i:i+len(T)]: return i raise ValueError("substring not found") def __getitem__(self,index): if index.__class__==int: if index<0: index+=len(self.string) assert 0<=index