Pagini recente » Cod sursa (job #104783) | Cod sursa (job #1309645) | Cod sursa (job #332016) | Cod sursa (job #2680532) | Cod sursa (job #2361518)
#include <bits/stdc++.h>
#define MOD1 666013
#define MOD2 1000000007
#define baza 53
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a;
string b;
int nr=0;
vector <int> answer;
int convert[128];
void cautare(){
long long hash1=0, hash2=0, hash3=0, hash4=0, i, j, n, m, pmax1=1, pmax2=1;
n=a.size();
m=b.size();
for(i=0;i<n;i++){
hash1*=baza;
hash1+=convert[a[i]];
hash1=hash1%MOD1;
hash2*=baza;
hash2+=convert[a[i]];
hash2=hash2%MOD2;
}
for(i=0;i<n;i++){
hash3*=baza;
hash3+=convert[b[i]];
hash3=hash3%MOD1;
hash4*=baza;
hash4+=convert[b[i]];
hash4=hash4%MOD2;
if(i<n-1){
pmax1*=baza;
pmax1=pmax1%MOD1;
pmax2*=baza;
pmax2=pmax2%MOD2;
}
}
if(hash1==hash3 && hash2==hash4){
nr++;
answer.push_back(0);
}
for(i=n;i<m;i++){
hash3-=((convert[b[i-n]])*pmax1)%MOD1-MOD1;
hash3=hash3%MOD1;
hash3*=baza;
hash3+=convert[b[i]];
hash3=hash3%MOD1;
hash4-=((convert[b[i-n]])*pmax2)%MOD2-MOD2;
hash4=hash4%MOD2;
hash4*=baza;
hash4+=convert[b[i]];
hash4=hash4%MOD2;
if(hash1==hash3 && hash2==hash4){
nr++;
answer.push_back(i-n+1);
}
}
fout<<nr<<"\n";
for(i=0;i<answer.size();i++)
fout<<answer[i]<<" ";
}
int main(){
int i;
fin>>a>>b;
for(i='A';i<='Z';i++)
convert[i]=i-'A'+1;
for(i='a';i<='z';i++)
convert[i]=i-'a'+27;
cautare();
return 0;
}