Pagini recente » Cod sursa (job #2933102) | Cod sursa (job #2549780) | Cod sursa (job #264511) | Cod sursa (job #2052351) | Cod sursa (job #3250486)
#include <iostream>
#include <math.h>
#include <string>
#include <fstream>
const int MAXN=2e6+3;
const int MOD=980926811;
const int BASE=333352352;
const int MAXK=1000;
int hasha[MAXN+1];
int hashb[MAXN+1];
int put[MAXN+1];
int anspoz[MAXK];
void init_hashes(std::string s, std::string s1){
int i, n, m;
n=s.size();
m=s1.size();
put[0]=1;
for(i=1; i<=MAXN; i++)
put[i]=1LL*put[i-1]*BASE%MOD;
for(i=1; i<=n; i++)
hasha[i]=(1LL*hasha[i-1]*BASE+s[i-1])%MOD;
for(i=1; i<=m; i++)
hashb[i]=(1LL*hashb[i-1]*BASE+s1[i-1])%MOD;
}
int get_hash(int l, int r, int v[]){
int ans=(v[r+1]-1LL*v[l]*put[r-l+1]%MOD+MOD)%MOD;
return ans;
}
int main()
{
std::ifstream cin("strmatch.in");
std::ofstream cout("strmatch.out");
int i, n, m, k;
std::string s, s1;
cin>>s>>s1;
init_hashes(s, s1);
n=s.size();
m=s1.size();
i=k=0;
while(i<=m-n && k<MAXK){
if(get_hash(0, n-1, hasha)==get_hash(i, i+n-1, hashb))
anspoz[k++]=i;
i++;
}
cout<<k<<"\n";
for(i=0; i<k; i++)
cout<<anspoz[i]<<" ";
return 0;
}