Pagini recente » Cod sursa (job #2968600) | Cod sursa (job #1051636) | Cod sursa (job #2399044) | Cod sursa (job #2535845) | Cod sursa (job #1265052)
#include <cstdio>
#include <cstring>
using namespace std;
#define lgmax 2000002
FILE *f=fopen ("strmatch.in","r");
FILE *g=fopen ("strmatch.out","w");
char a[lgmax],b[lgmax];
int pi[lgmax],sl[1001],sol;
void prefix (char s[],int lg){
int k=0;
for (int i=2;i<=lg;++i){
while (k>0 && s[i]!=s[k+1]) k=pi[k];
if (s[i]==s[k+1]) k++;
pi[i]=k;
}
}
void match (char a[],char b[],int lga,int lgb){
// lga<lgb
int k=0;
for (int i=1;i<=lgb;++i){
while (k>0 && a[k+1]!=b[i]) k=pi[k];
if (a[k+1]==b[i]) k++;
if (k==lga){
sol++;
if (sol<=1000) sl[sol]=i-k;
}
}
}
int main(){
int lga,lgb;
fscanf (f,"%s%*c",a+1);
fscanf (f,"%s",b+1);
lga=strlen(a+1);
lgb=strlen(b+1);
if (lga>lgb){
fprintf (g,"%d",0);
return 0;
}
prefix(a,lga);
match (a,b,lga,lgb);
int go= sol<=1000?sol:1000;
fprintf (g,"%d\n",sol);
for (int i=1;i<=go;++i) fprintf (g,"%d ",sl[i]);
return 0;
}