Pagini recente » Cod sursa (job #768256) | Cod sursa (job #1006171) | Cod sursa (job #1327393) | Borderou de evaluare (job #156616) | Cod sursa (job #675490)
Cod sursa(job #675490)
#include<stdio.h>
#include<string.h>
#define minim(a, b) ((a < b) ? a : b)
char s[2000010],s1[2000010];
int pi[2000010],n,m,nr,poz[2000010],p;
void citire()
{
FILE*f=fopen("strmatch.in","r");
fgets(s,2000000,f);
fgets(s1,2000000,f);
for(;(s[n]>='A'&&s[n]<='Z')||(s[n]>='a'&&s[n]<='z')||(s[n]>='0'&&s[n]<='9');++n);
for(;(s1[m]>='A'&&s1[m]<='Z')||(s1[m]>='a'&&s1[m]<='z')||(s1[m]>='0'&&s1[m]<='9');++m);
for (int i = m; i; --i) s1[i] = s1[i-1]; s1[0] = ' ';
for (int i = n; i; --i) s[i] = s[i-1]; s[0] = ' ';
fclose(f);
}
void kmp_prefix()
{
pi[1]=0;
int k=0;
for(int i=2;i<=n;++i)
{
while(k>0 && s[k+1]!=s[i])
k=pi[k];
if(s[k+1] == s[i] )
{ ++k; }
pi[i]=k;
}
}
void kmp()
{
int k=0;
for(int i=1;i<=m;++i)
{
while(k>0 && s[k+1]!=s1[i])
{ k=pi[k]; ; }
if(s[k+1]==s1[i])
{ ++k; }
if(k == n)
{
k=pi[n];
++nr;
if(nr<=1000)
poz[nr]=i-n;
}
}
}
int main()
{
citire();
kmp_prefix();
kmp();
FILE*f=fopen("strmatch.out","w");
fprintf(f,"%d\n",nr);
for(int i=1;i<=minim(nr,1000);++i) fprintf(f,"%d ",poz[i]);
fclose(f);
return 0;
}