Pagini recente » Cod sursa (job #2744496) | Cod sursa (job #733726) | Cod sursa (job #297278) | Cod sursa (job #560249) | Cod sursa (job #723610)
Cod sursa(job #723610)
#include <cstdio>
#include <cstring>
#include <vector>
#define CMax 2000021
using namespace std;
char s1[CMax],s2[CMax];
int lg1,lg2,n,k,Hash,obj_Hash,nr;
vector<int> ve;
int make_Hash(long lo,long hi,char s[]) {
int Hash=0;
//Hash code
for(long i=lo;i<=hi;i++)
Hash+=s[i]-65;
return Hash;
}
int remake_Hash(int Hash,char c1,char c2) {
//Hash code
Hash-=c1-c2;
return Hash;
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",s1,s2);
lg1=strlen(s1);
lg2=strlen(s2);
Hash=make_Hash(0,lg1-1,s2);
obj_Hash=make_Hash(0,lg1-1,s1);
while(k+lg1<=lg2) {
if(Hash==obj_Hash)
if(!strncmp(s1,s2+k,lg1)) {
nr++;
if(nr<=1000)
ve.push_back(k);
}
Hash=remake_Hash(Hash,s2[k],s2[k+lg1]);
k++;
}
printf("%ld\n",nr);
for(long i=0;i<ve.size();i++)
printf("%ld ",ve[i]);
printf("\n");
return 0;
}