Pagini recente » Cod sursa (job #877128) | Cod sursa (job #2549629) | Cod sursa (job #2819343) | Cod sursa (job #581889) | Cod sursa (job #723627)
Cod sursa(job #723627)
#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,i,j;
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);
for(i=1;s2[i-1]==s2[i];i++);
for(j=1;s1[j-1]==s1[j];j++);
if(i==lg2 && j==lg1 && s1[0]==s2[0]) {
printf("%d\n",lg2-lg1);
for(long i=0;i<=999;i++)
printf("%d ",i);
}
else {
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("%d\n",nr);
for(long i=0;i<ve.size();i++)
printf("%d ",ve[i]);
printf("\n");
}
return 0;
}