Pagini recente » Cod sursa (job #801317) | Cod sursa (job #350302) | Cod sursa (job #390096) | Cod sursa (job #3122728) | Cod sursa (job #1015633)
# include <iostream>
# include <fstream>
# include <string.h>
# define nmax 2000000
using namespace std;
char s[nmax],n,m,w[nmax],f[nmax];
int nr;
ifstream fin("strmatch.in");
ofstream g("strmatch.out");
void table()
{
int i,j;
f[0]=f[1]=0;
for(i=2; i<=m; i++)
{
j=f[i-1];
for( ; ; )
{
if(w[i-1]==w[j])
{
f[i]=j+1;
break;
}
else
{
if(j==0)
{
f[i]=0;
break;
}
j=f[j];
}
}
}
}
void cauta()
{
int i=0,j=0;
while(j<=n)
{
if(w[i]==s[j])
{
i++;
j++;
if(i==m)
{
nr+=1;
i=0;
i=f[i];
}
}
else
{
if(i>0)
i=f[i];
else
j+=1;
}
}
}
int main()
{
fin.getline(w,nmax);
fin.getline(s,nmax);
m=strlen(w);
n=strlen(s);
table();
cauta();
g<<nr<<'\n';
return 0;
}