Pagini recente » Cod sursa (job #3123088) | Cod sursa (job #628401) | Cod sursa (job #1032798) | Cod sursa (job #541872) | Cod sursa (job #1248314)
#include <cstdio>
#define maxl 2000010
#include <cstring>
#include <queue>
#include <ctype.h>
using namespace std;
char a[maxl],b[maxl];
long p[maxl];
queue <long> qu;
long apn=0;
long la,lb;
void start(){
long k=0;
p[0]=0;
for(long i=2;i<=la;i++){
while(k&&(a[k+1]!=a[i]))
k=p[k];
if(a[k+1]==a[i])
++k;
p[i]=k;
}
}
void solve(){
long k=0;
start();
for(long i=1;i<=lb;i++){
while(k&&(a[k+1]!=b[i]))
k=p[k];
if(a[k+1]==b[i])
++k;
if(k==la){
apn++;
if(apn<1000)
qu.push(i-la);
k=p[k];
}
}
}
void print(){
printf("%ld\n",apn);
if(apn>1000)
apn=1000;
while(apn--){
printf("%ld ",qu.front());
qu.pop();
}
}
void mvstr(char x[],long a){
long i;
for(i=a;i>0;i--)
x[i]=x[i-1];
}
int main(void){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
la=strlen(a)-1;
lb=strlen(b)-1;
mvstr(a,la);
mvstr(b,lb);
solve();
print();
}