Pagini recente » Cod sursa (job #1818360) | Cod sursa (job #407865) | Cod sursa (job #801068) | Cod sursa (job #2777433) | Cod sursa (job #2419074)
#include <bits/stdc++.h>
#define MAX 1005
#define BAZA 61
#define MOD (long long)(1e9+7)
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long Ans[MAX],n,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;
if(a[i]>='A'&&a[i]<='Z')
hashA+=a[i]-'A';
else hashA+=a[i]-'a'+27;
if(hashA>MOD)hashA%=MOD;
}
for(i=0;i<sza;++i){
hashB=hashB*BAZA;
if(b[i]>='A'&&b[i]<='Z')
hashB+=b[i]-'A';
else hashB+=b[i]-'a'+27;
if(hashB>MOD)hashB%=MOD;
}
if(hashA==hashB) Ans[n++]=0;
for(i=sza;i<szb;++i){
if(b[i]>='A'&&b[i]<='Z')
y=b[i]-'A';
else y=b[i]-'a'+27;
if(b[i-sza]>='A'&&b[i-sza]<='Z')
x=b[i-sza]-'A';
else x=b[i-sza]-'a'+27;
hashB=(hashB-x*putere+MOD)%MOD*BAZA+y;
if(hashA>MOD)hashA%=MOD;
if(hashB>MOD)hashB%=MOD;
if(hashA==hashB) Ans[n++]=i-sza+1;
}
}
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<n;++i)
fout<<Ans[i]<<' ';
fout<<'\n';
}