Pagini recente » Cod sursa (job #2942647) | Cod sursa (job #1032784) | Cod sursa (job #306375) | Cod sursa (job #1049951) | Cod sursa (job #1264961)
#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 (pi[i]==pi[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);
prefix(a,lga);
match (a,b,lga,lgb);
fprintf (g,"%d\n",sol);
for (int i=1;i<=sol;++i) fprintf (g,"%d ",sl[i]);
return 0;
}