Pagini recente » Cod sursa (job #1462302) | Cod sursa (job #2405945) | Cod sursa (job #1689518) | Cod sursa (job #1428743) | Cod sursa (job #1514718)
#include <cstdio>
#include <cstring>
using namespace std;
const int nmx = 2000005;
const int mmx = 1000;
char s[nmx],p[nmx], s_size, p_size;
int prefix[nmx],af[mmx+2];
void make_prefix(){
int i = 0, j = 1;
while(j < p_size){
if(p[i] != p[j])
if(i)
i = prefix[i-1];
else
++ j;
else{
prefix[j] = ++i;
++ j;
}
}
}
void kmp(){
int i = 0, j = 0;
while(j < s_size && af[0] < mmx){
if(s[j] != p[i])
if(i)
i = prefix[i-1];
else
++ j;
else{
++ i;
++ j;
if(i == p_size)
af[++af[0]] = j-p_size;
}
}
}
void output(){
printf("%d\n", af[0]);
for(int i = 1; i <= af[0]; ++i)
printf("%d ", af[i]);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s",p, s);
p_size = strlen(p);
s_size = strlen(s);
make_prefix();
kmp();
output();
return 0;
}