Pagini recente » Cod sursa (job #2578041) | Cod sursa (job #3248841) | Cod sursa (job #2957067) | Cod sursa (job #802779) | Cod sursa (job #2419084)
#include <bits/stdc++.h>
#define MAX 1005
#define BAZA 31
#define MOD (long long)(1e9+7)
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long Ans[MAX],n,nr,sza,szb,hashA,hashB,x,y;
string a,b;
void afisare();
void rezolvare();
long long Exp(long long,long long);
int main(){
fin>>a>>b;
rezolvare();
afisare();
return 0;
}
void rezolvare(){
long long i,putere;
sza=a.size();
szb=b.size();
if(szb<sza)return;
putere=Exp(BAZA,sza-1);
for(i=0;i<sza;++i){
hashA=hashA*BAZA;
hashA+=a[i];
if(hashA>MOD)hashA%=MOD;
}
for(i=0;i<sza;++i){
hashB=hashB*BAZA;
hashB+=b[i];
if(hashB>MOD)hashB%=MOD;
}
if(hashA==hashB) Ans[n++]=0;
for(i=sza;i<szb;++i){
x=b[i-sza];
y=b[i];
hashB=(hashB-x*putere+MOD)%MOD*BAZA+y;
if(hashA>MOD)hashA%=MOD;
if(hashB>MOD)hashB%=MOD;
if(hashA==hashB){
if(nr<1000)Ans[nr++]=i-sza+1;
++n;
}
}
}
long long Exp(long long x,long long n){
long long p=1;
while(n){
if(n%2){
p*=x;
--n;
if(p>MOD)p%=MOD;
}
x*=x;
n/=2;
if(x>MOD)x%=MOD;
}
return (p%MOD);
}
void afisare(){
long long i;
fout<<n<<'\n';
for(i=0;i<nr;++i)
fout<<Ans[i]<<' ';
fout<<'\n';
}