Pagini recente » Cod sursa (job #2628085) | Cod sursa (job #1778155) | Cod sursa (job #197817) | Cod sursa (job #328120) | Cod sursa (job #427607)
Cod sursa(job #427607)
#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 73
#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);
lenb=strlen(b);
if (lena>lenb){
printf("0\n");
return 0;
}
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<lenb;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;
}