Pagini recente » Cod sursa (job #2354411) | Cod sursa (job #646112) | Cod sursa (job #2221610) | Cod sursa (job #3254819) | Cod sursa (job #99724)
Cod sursa(job #99724)
#include<stdio.h>
#include<string.h>
typedef struct nod {nod* c[3];} nod;
nod *p;
char N[30],M[10000010];
int pi[30];
int i;
long long nr;
//kmp comparare siruri
void PI()
{int k=0,i,n=strlen(N);
pi[0]=pi[1]=0;
for(i=1;i<n;i++)
{while(k>0&&N[k]!=N[i])
k=pi[k];
if(N[k]==N[i]) k++;
pi[i+1]=k;}}
int KMP()
{int n=strlen(N),m=strlen(M),i,k=0,nr=0;
PI();
for(i=0;i<m;i++)
{while(k>0&&N[k]!=M[i])
k=pi[k];
if(N[k]==M[i]) k++;
if(k==n) nr++; }
return nr;}
nod* new_nod()
{nod *q=new nod;
q->c[0]=q->c[1]=q->c[2]=0;
return q;}
//verificare daca cuv exista deja
int new_word()
{int n=strlen(N),i;
nod *q=p;
int ok=0;
for(i=0;i<n;i++)
{if(!q->c[N[i]-'a'])
{q->c[N[i]-'a']=new nod;
(q->c[N[i]-'a'])->c[0]=(q->c[N[i]-'a'])->c[1]=(q->c[N[i]-'a'])->c[2]=0;
ok=1;}
q=q->c[N[i]-'a'];}
return ok;}
int main()
{freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
p=new nod; p->c[0]=p->c[1]=p->c[2]=0;
scanf(" %s ",M);
while(!feof(stdin))
{scanf(" %s ",N);
if(new_word())
nr=nr+KMP();
}
printf("%lld",nr);
fclose(stdout);
return 0;}