Cod sursa(job #3177193)

Utilizator Luijika_programatorulBursuc Luigi Luijika_programatorul Data 28 noiembrie 2023 17:49:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define int long long
int B;
const int MOD = 1e9+7;
struct HashedString{
	vector<int> hash,p;
	string s;
	HashedString(string S){
		s = '_' + S;
		hash.resize(s.size()+1);
		
		p.push_back(1);
		for(int i=1;i<=S.size()+3;++i){
			p.push_back(((p.back()%MOD) * (B%MOD)) % MOD);
		}

		for(int i=1;i<=s.size()-1;++i){
			hash[i] = (((hash[i-1]%MOD) * (B%MOD)) + s[i]) % MOD;
		}
	}
	long long getHash(int st ,int  dr){
		long long raw_val = (hash[dr] - ((hash[st-1]%MOD) * (p[dr-st+1]%MOD))%MOD + MOD) % MOD;
		return raw_val % MOD;
	}
};
signed main() {
  srand(time(nullptr));
  B = rand();
  string a,b;
  fin >> a >> b;

  int n = a.size();
  int m = b.size();
  HashedString hash_a(a);
  HashedString hash_b(b);

  long long A_HASH = hash_a.getHash(1,n);

  long long st=1,dr=n;
  vector<long long> ap;
  while(dr<=m){
    if(hash_b.getHash(st,dr) == A_HASH){
      ap.push_back(st-1);
    }

    st++,dr++;
  }
  fout<<ap.size()<<'\n';
  for(int i=0;i<ap.size() && i< 1000; ++i){
    fout<<ap[i]<<' ';
  }
  return 0;
}