Pagini recente » Cod sursa (job #1490773) | Cod sursa (job #2254613) | Cod sursa (job #1398837) | Cod sursa (job #1490777) | Cod sursa (job #1199215)
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 2000002
char s[MAX], p[MAX];
int pi[MAX], n, m, sol[1001], nsol;
void prefix();
void kmp();
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", p+1, s+1);
n = strlen(s+1); m = strlen(p+1);
prefix();
kmp();
printf("%d\n", nsol);
if(nsol>1000) nsol = 1000;
for(int i=1; i<=nsol; i++) printf("%d ", sol[i]);
return 0;
}
void kmp(){
int q=0;
for(int i=1; i<=n; i++){
while(q>0 and p[q+1]!=s[i])
q = pi[q];
if(p[q+1]==s[i])
q++;
if(q==m){
nsol++;
if(nsol<=1000) sol[nsol] = i-m;
q = pi[q];
}
}
}
void prefix(){
int q, k;
k = pi[1] = 0;
for(q=2; q<=m; q++){
while(k>0 and p[k+1]!=p[q])
k = pi[k];
if(p[k+1]==p[q]) k++;
pi[q] = k;
}
}