Pagini recente » Cod sursa (job #2456240) | Cod sursa (job #2592520) | Cod sursa (job #2865925) | Cod sursa (job #166809) | Cod sursa (job #1514721)
#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 && 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;
}