Pagini recente » Cod sursa (job #2296133) | Cod sursa (job #2630939) | Cod sursa (job #982994) | Cod sursa (job #2888535) | Cod sursa (job #478923)
Cod sursa(job #478923)
#include <cstdio>
#include <vector>
#define NN 2000005
using namespace std;
char P[NN],T[NN];
int pi[NN];
vector <int> match;
inline void prefix(){
int k=0,m;
m=strlen(P+1);
pi[1]=0;
for(int q=2;q<=m;q++){
while(k>0 && (P[k+1] != P[q]))
k=pi[k];
if(P[k+1] == P[q])
k++;
pi[q]=k;
}
}
inline void kmp(){
int q=0,m=strlen(P+1),n=strlen(T+1);
for(int i=1;i<=n;i++){
while(q>0 && P[q+1] != T[i])
q=pi[q];
if(P[q+1] == T[i])
q++;
if(q==m){
match.push_back(i-m);
q=pi[q];
}
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(P+1);
gets(T+1);
prefix();
kmp();
printf("%d\n",match.size());
int cnt=0;
for(vector <int> :: iterator it = match.begin(); it != match.end() && cnt<1000; it++,cnt++){
printf("%d ",*it+1);
}
return 0;
}