Pagini recente » Cod sursa (job #81159) | Cod sursa (job #470511) | Cod sursa (job #224235) | Cod sursa (job #2695798) | Cod sursa (job #1983861)
#include <cstdio>
#include <cstring>
#define lmax 2000010
using namespace std;
char pattern[lmax];
char s[lmax];
int pref[lmax],poz[lmax],i,j,n,m,noccur=0;
int main()
{
FILE *f=fopen("strmatch.in","r");
fscanf(f,"%s%s",pattern,s);
n=strlen(s);
m=strlen(pattern);
i=1;
j=0;
pref[0]=0;
while(pattern[i])
if(pattern[i]==pattern[j])
pref[i++]=++j;
else if(j==0)
pref[i++]=0;
else
j=pref[j-1];
i=0;
j=0;
while(s[i])
if(s[i]==pattern[j])
{
++i,++j;
if(pattern[j]==0)
{
poz[++noccur]=i-m;
j=pref[j-1];
}
}
else if(j==0)i++;
else j=pref[j-1];
fclose(f);
f=fopen("strmatch.out","w");
fprintf(f,"%d\n",noccur);
if(noccur>1000)noccur=1000;
for(i=1;i<=noccur;i++)
fprintf(f,"%d ",poz[i]);
return 0;
}