Pagini recente » Cod sursa (job #1563992) | Cod sursa (job #222839) | Cod sursa (job #217751) | Monitorul de evaluare | Cod sursa (job #2190924)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define MAX 2000000
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(int i, int j){
initurm();
for(i,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;
KMP(i-j+1,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(0,0);
write();
return 0;
}