Pagini recente » Cod sursa (job #1470646) | Cod sursa (job #1046818) | Cod sursa (job #1008845) | Cod sursa (job #3307292) | Cod sursa (job #3305995)
//cu hash
#include <fstream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
unsigned int hashes[2000005], base=257;
unsigned int powar[2000005];
void buildh( string b){
unsigned int n=b.size();
for(unsigned int i=n;i>=1;i--){
hashes[i]=(hashes[i+1]*base + b[i-1]);
}
}
void buildp(string b){
unsigned int n=b.size();
powar[0]=1;
for(unsigned int i=1;i<=n;i++){
powar[i]=powar[i-1]*base;
}
}
unsigned int buildpathash(string a){
unsigned int n=a.size() , hashs=0;
for(unsigned int i=n;i>=1;i--){
hashs=hashs*base+a[i-1];
}
return hashs;
}
unsigned int buildbhash(unsigned int lf , unsigned int rg){
return ( hashes[lf]- hashes[rg+1]* powar[rg-lf+1]);
}
bool patmatch ( unsigned int hashs, unsigned int lf , unsigned int rg){
return hashs==buildbhash(lf,rg);
}
int main(){
string a,b;
cin>>a>>b;
buildh(b);
buildp(b);
unsigned int hashs= buildpathash(a) , cnt=0;
for(unsigned int i=1;i+a.size()-1 <=b.size();i++){
if(patmatch(hashs,i,i+a.size()-1)) cnt++;
}
cout<<cnt<<endl;
unsigned int asize, bsize;
asize=a.size();
bsize=b.size();
for(unsigned int j=1;j+asize-1<=bsize;j++){
if(cnt<1000 && patmatch(hashs,j,j+asize-1)){
cnt++;
cout<<j-1<<" ";
}
}
}