Pagini recente » Cod sursa (job #1752751) | Cod sursa (job #3004202) | Cod sursa (job #166881) | Cod sursa (job #2367463) | Cod sursa (job #430904)
Cod sursa(job #430904)
#include<fstream.h>
#include<string.h>
char s1[2000002],s2[2000002];
int n,m,nr,v[1005],pi[2000002],min;
void afisare ()
{
ofstream g("strmatch.out");
g<<nr<<'\n';
if (nr>1000)
nr=1000;
for (int i=1;i<=nr;i++)
g<<v[i]<<' ';
g.close();
}
void kmp ()
{
int i,j;
j=0;
for (i=0;i<n;i++)
{
while (j>0 && s1[i]!=s2[j+1])
j=pi[j];
if (s1[i]==s2[j+1])
j++;
if (j==m-1)
{
nr++;
if (nr<=1000)
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;
}