Pagini recente » Cod sursa (job #191713) | Cod sursa (job #3032768) | Cod sursa (job #2931694) | Cod sursa (job #2100767) | Cod sursa (job #2532468)
#include <bits/stdc++.h>
#define nmax 1024
#define hmax 105
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<int> sol;
int nrHash=2;
long long cst[hmax];
long long ncst[hmax];
long long p[hmax];
long long mod[hmax];
long long pw[hmax];
void init(){
/*for(int i=0; i<nrHash; i++){
mod[i] = 100000000 + rand()%100000000;
pw[i] = 20 + rand()%23;
p[i] = 1;
}*/
mod[0] = 698695723;
mod[1] = 536557673;
p[0]= 1;
p[1]= 1;
pw[0]= 21564321;
pw[1]= 21564321;
}
bool verif(){
for(int i=0; i<nrHash; i++){
if(cst[i]!=ncst[i]) return false;
}
return true;
}
void afis(){
out << sol.size() << '\n';
for(auto x:sol) out << x << ' ';
}
void read(){
in >> a >> b;
for(int i=0; i<a.size(); i++){
for(int j=0; j<nrHash; j++){
cst[j]=(cst[j]*pw[j] + a[i])%mod[j];
p[j]=p[j]*pw[j]%mod[j];
}
}
if(b.size()<a.size()){
out << "0";
exit(0);
}
for(int i=0; i<a.size(); i++){
for(int j=0; j<nrHash; j++){
ncst[j] = (ncst[j]*pw[j]+b[i])%mod[j];
}
}
for(int i=a.size(); i<b.size(); i++){
if(verif()){
sol.push_back(i-a.size());
if(sol.size()==1000){
afis();
exit(0);
}
}
for(int j=0; j<nrHash; j++){
ncst[j] = (mod[j] + ncst[j]*pw[j] - b[i-a.size()]*p[j]%mod[j] + b[i])%mod[j];
}
}
afis();
}
int main(){
init();
read();
}