Pagini recente » Cod sursa (job #1079902) | Borderou de evaluare (job #514519) | Cod sursa (job #310452) | Borderou de evaluare (job #347856) | Cod sursa (job #1689209)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N,M,i,t1,t2,e1,e2,h1,h2,k;
char A[2000010],B[2000010];
int v[1010];
int main(){
fin>>A>>B;
N=strlen(A);
M=strlen(B);
e1=e2=1;
for(i=0;i<N;i++){
h1=(h1*27+A[i])%100009;
h2=(h2*29+A[i])%666013;
if(i!=0){
e1=(e1*27)%100009;
e2=(e2*29)%666013;
}
}
if(N>M){
fout<<"0";
return 0;
}
for(i=0;i<N;i++){
t1=(t1*27+B[i])%100009;
t2=(t2*29+B[i])%666013;
}
if(t1==h1&&t2==h2)
v[++k]=0;
for(i=N;i<M;i++){
t1=((t1-(B[i-N]*e1)%100009+100009)*27+B[i])%100009;
t2=((t2-(B[i-N]*e2)%666013+666013)*29+B[i])%666013;
if(t1==h1&&t2==h2){
k++;
if(k<=1000)
v[k]=i-N+1;
}
}
fout<<k<<"\n";
for(i=1;i<=1000&&i<=k;i++)
fout<<v[i]<<" ";
return 0;
}