Pagini recente » Cod sursa (job #1699318) | Cod sursa (job #3033196) | Cod sursa (job #622961) | Cod sursa (job #1728035) | Cod sursa (job #478920)
Cod sursa(job #478920)
#include <cstdio>
#include <vector>
#define NN 2000005
using namespace std;
char P[NN],T[NN];
int pi[NN],cnt;
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){
cnt++;
match.push_back(i-q);
}
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(P+1);
gets(T+1);
prefix();
kmp();
printf("%d\n",cnt);
cnt=0;
for(vector <int> :: iterator it = match.begin(); it != match.end() && cnt<=1000; it++,cnt++){
printf("%d ",*it+1);
}
return 0;
}