Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Solution
- {
- int mul=256,mod=107;
- public:
- vector <int> search(string pat, string txt)
- {
- int lenTxt=txt.length(),lenPat=pat.length();
- if(lenTxt<lenPat)return {-1};
- vector<int>pos;
- int patHash=0,txtHash=0,hash=1;
- for(int i=1;i<=lenPat-1;i++){
- hash=(hash*mul)%mod;
- }
- for(int i=0;i<lenPat;i++){
- patHash=(patHash*mul + pat[i])%mod;
- txtHash=(txtHash*mul + txt[i])%mod;
- }
- for(int i=0;i<=lenTxt-lenPat;i++){
- if(patHash==txtHash){
- int present=true;
- for(int j=0;j<lenPat;j++){
- if(txt[i+j] != pat[j]){
- present=false;
- break;
- }
- }
- if(present==true)pos.push_back(i+1);
- }
- if(i<lenTxt-lenPat){
- txtHash=((txtHash- (txt[i]*hash)%mod )*mul + txt[i+lenPat])%mod;
- if(txtHash<0)txtHash+=mod;
- }
- }
- if(pos.size()==0)return {-1};
- return pos;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement