Pagini recente » Cod sursa (job #211082) | Cod sursa (job #571784) | Cod sursa (job #2047159) | Cod sursa (job #1050429) | Cod sursa (job #1382943)
#include <fstream>
#include <cstring>
#include <cstdio>
#define LGMAX 2000001
using namespace std;
ofstream fout("strmach.out");
int d,lg,k,L[LGMAX],poz,nr;
char a[LGMAX],b[LGMAX];
void prefix()
{
d=strlen(a);
L[0]=-1;
for(int i=1;i<d;i++)
{
k=L[i-1];
while(k>-1 && a[k+1]!=a[i])
k=L[k];
if(a[k+1]==a[i])
k++;
L[i]=k;
}
}
void kmp()
{
lg=strlen(b);
poz=0;
for(int i=0;i<lg;i++)
{
if(poz==d)
nr++,poz=L[poz]+1;
if(a[poz]==b[i])
poz++;
else
poz=L[poz]+1;
}
fout<<nr<<'\n';
}
int main()
{
freopen("strmach.in","r",stdin);
scanf("%s",&a);
scanf("%s",&b);
prefix();
kmp();
return 0;
}