Pagini recente » Cod sursa (job #2732599) | Cod sursa (job #2259094) | Cod sursa (job #2611706) | Cod sursa (job #1314127) | Cod sursa (job #2976410)
#include <fstream>
#include <cstring>
#define MOD 1000007
#define B 26
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int i, j, n, m, n1, n2, hash1, hash2, pow, k;
char a[2000002], b[2000002];
int sol[1002];
int main() {
cin>>a>>b;
n1=strlen(a);
n2=strlen(b);
if(n1>n2){
cout<<0;
return 0;
}
pow=1;
for(i=0;i<n1;i++){
hash1=(hash1*B+a[i])%MOD;
if(i<n1-1){
pow=pow*B;
pow=pow%MOD;
}
}
for(i=0;i<n1;i++){
hash2=(hash2*B+b[i])%MOD;
}
if(hash1==hash2)
sol[++k]=0;
for(i=n1;i<n2;i++){
hash2=hash2-pow*b[i-n1];
if(hash2<0)
hash2+=MOD;
hash2=(hash2*B+b[i])%MOD;
if(hash2==hash1){
sol[++k]=i-n1+1;
}
}
cout<<k<<"\n";
for(i=1;i<=min(k, 1000);i++)
cout<<sol[i]<<" ";
}