Pagini recente » Cod sursa (job #772919) | Cod sursa (job #3179912) | Cod sursa (job #1809144) | Cod sursa (job #791357) | Cod sursa (job #1015627)
# 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;
j=j-strlen(w)+1;
}
}
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();
cout<<nr;
return 0;
}