Pagini recente » Cod sursa (job #985334) | Cod sursa (job #2085562) | Cod sursa (job #1088145) | Cod sursa (job #2575885) | Cod sursa (job #1364496)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char s[2000002],t[2000002];
int pi[2000002],d[2000002],m,n,nr,poz[1005];
void Citire()
{
fscanf(f,"%s",&t);
fscanf(f,"%s",&s);
n=strlen(s);
m=strlen(t);
}
void Precalculare()
{
int i,k=0;
pi[0]=0;
for(i=1; i<m; i++)
{
if(t[i]==t[k]) k++;
else
{
while(k>0 && t[k]!=t[i])
k=pi[k-1];
if(t[k]==t[i]) k++;
}
pi[i]=k;
}
}
void KMP()
{
int i,k=0;
for(i=0; i<n; i++)
if(s[i]==t[i]) k++;
else
{
while(k>0 && t[k]!=s[i])
k=pi[k-1];
if(t[k]==s[i]) k++;
d[i]=k;
if(k==m)
{
nr++;
if(nr<=1000)
poz[nr]=i-m+1;
}
}
}
void Afisare()
{int i;
fprintf(g,"%d\n",nr);
if(nr<=1000)
for(i=1;i<=nr;i++)
fprintf(g,"%d ",poz[i]);
else
for(i=1;i<=1000;i++)
fprintf(g,"%d ",poz[i]);
}
int main()
{
Citire();
Precalculare();
KMP();
Afisare();
fclose(f);
fclose(g);
return 0;
}