Pagini recente » Cod sursa (job #163881) | Cod sursa (job #381335) | Cod sursa (job #744120) | Cod sursa (job #1935161) | Cod sursa (job #430881)
Cod sursa(job #430881)
#include<fstream.h>
#include<string.h>
char s1[2000002],s2[2000002];
int n,m,nr,v[1005],pi[2000002];
void afisare ()
{
ofstream g("strmatch.out");
g<<nr<<'\n';
for (int i=1;i<=nr;i++)
g<<v[i]<<' ';
g.close();
}
void kmp ()
{
int i,j;
j=0;
for (i=0;i<n && nr<1000;i++)
{
while (j>0 && s1[i]!=s2[j+1])
j=pi[j];
if (s1[i]==s2[j+1])
j++;
if (j==m-1)
v[++nr]=i-m+2,j=pi[j];
}
}
void prefix ()
{
int i,j;
for (i=2;i<m;i++)
{
j=pi[i-1];
while (j>0 && s2[j+1]!=s2[i])
j=pi[j];
if (s2[j+1]==s2[i])
j++;
pi[i]=j;
}
}
void citire ()
{
ifstream f ("strmatch.in");
f>>s1;
s2[0]='#';
s2[1]=0;
strcat(s2,s1);
f>>s1;
n=strlen(s1);
m=strlen(s2);
f.close();
}
int main()
{
citire ();
prefix();
kmp();
afisare ();
return 0;
}