Pagini recente » Cod sursa (job #2978026) | Cod sursa (job #2232511) | Cod sursa (job #2205062) | Cod sursa (job #2491265) | Cod sursa (job #1514723)
#include <cstdio>
#include <cstring>
using namespace std;
const int nmx = 2000005;
const int mmx = 1000;
char s[nmx],p[nmx];
int prefix[nmx],af[mmx+2],s_size, p_size;
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) {
if(s[j] != p[i])
if(i)
i = prefix[i-1];
else
++ j;
else {
++ i;
++ j;
if(i == p_size) {
++ af[0];
if(af[0] <= mmx)
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;
}