Pagini recente » Cod sursa (job #3128978) | Cod sursa (job #1304027) | Cod sursa (job #695563) | Cod sursa (job #1605443) | Cod sursa (job #427606)
Cod sursa(job #427606)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
void open(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
};
#define MOD1 3089
#define MOD2 50093
#define pb push_back
#define sz size()
char a[2000010],b[2000010];
int lena,sub1,sub2,hash1,hash2,hash3,hash4,ans,v[2000010];
int main(){
open();
gets(a);gets(b);
sub1=sub2=1;
lena=strlen(a);
for (int i=0;i<lena;i++){
hash1=hash1*MOD1+a[i];
hash2=hash2*MOD2+a[i];
hash3=hash3*MOD1+b[i];
hash4=hash4*MOD2+b[i];
sub1*=MOD1;
sub2*=MOD2;
}
ans=0;
if (hash1==hash3 && hash2==hash4){
v[ans++]=0;
}
for (int i=lena;i<strlen(b);i++){
hash3=hash3*MOD1-sub1*b[i-lena]+b[i];
hash4=hash4*MOD2-sub2*b[i-lena]+b[i];
if (hash1==hash3 && hash2==hash4){
v[ans++]=i-lena+1;
}
}
printf("%d\n",ans);
if (ans){
for (int i=0;i<ans;i++){
if (i) printf(" ");
printf("%d",v[i]);
}
printf("\n");
}
return 0;
}