Pagini recente » Cod sursa (job #619412) | Cod sursa (job #1437566) | Cod sursa (job #1638175) | Cod sursa (job #1435211) | Cod sursa (job #2190928)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define MAX 2000050
int urmator[MAX],N,M,K=0,SOL[MAX];
char s[MAX], cuv[MAX];
void read(){
cin>>cuv;
cin>>s;
N=strlen(s);
M=strlen(cuv);
}
void initurm(){
int i,j;
urmator[0]=-1;
j=-1;
for(int i=0;i<M;i++,j++,urmator[i]=j)
while(j>=0&&cuv[i]!=cuv[j])
j=urmator[j];
}
void KMP(){
initurm();
for(int i=0,j=0;i<N&&j<M;i++,j++){
while(j>=0&&s[i]!=cuv[j])
j=urmator[j];
if(j==M-1){
SOL[++K]=i-j;
j=0;
}
}
}
void write(){
cout<<K<<'\n';
if(K>1000)
for(int i=1;i<=1000;i++)
cout<<SOL[i]<<" ";
else
for(int i=1;i<=K;i++)
cout<<SOL[i]<<" ";
}
int main(){
read();
KMP();
write();
return 0;
}