Pagini recente » Borderou de evaluare (job #1330994) | Cod sursa (job #2683704) | Cod sursa (job #400402) | Borderou de evaluare (job #276502) | Cod sursa (job #237510)
Cod sursa(job #237510)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define mod1 1000007
#define mod2 1000023
using namespace std;
char a[10000001],cuv[21];
long treila1[21],treila2[21],val1[10000001],val2[10000001];
int nrap;
long h1(int m, char *s)
{
int i,prod=0;
for(i=0;i<m;i++)
prod=(prod+treila1[m-i-1]*(s[i]-'a'))%mod1;
return prod;
}
long h2(int m, char *s)
{
int i,prod=0;
for(i=0;i<m;i++)
prod=(prod+treila2[m-i-1]*(s[i]-'a'))%mod2;
return prod;
}
int main()
{
int i,n,m;
vector <long> hash1,hash2;
hash1.reserve(50001);
hash2.reserve(50001);
FILE *f=fopen("abc2.in","r");
freopen("abc2.out","w",stdout);
fscanf(f,"%s\n",a);
fscanf(f,"%s\n",cuv);
n=strlen(a);
m=strlen(cuv);
treila1[0]=treila2[0]=1;
for(i=1;i<=20;i++)
{
treila1[i]=(treila1[i-1]*3)%mod1;
treila2[i]=(treila2[i-1]*3)%mod2;
}
hash1.push_back(h1(m,cuv));
hash2.push_back(h2(m,cuv));
while(!feof(f))
{
fscanf(f,"%s",cuv);
hash1.push_back(h1(m,cuv));
hash2.push_back(h2(m,cuv));
}
sort(hash1.begin(),hash1.end());
sort(hash1.begin(),hash1.end());
val1[0]=h1(m,a);
val2[0]=h2(m,a);
if(find(hash1.begin(),hash1.end(),val1[0])!=hash1.end()&&find(hash2.begin(),hash2.end(),val2[0])!=hash2.end())
nrap++;
for(i=1;i<=n-m+1;i++)
{ val1[i]=((val1[i-1]-treila1[m-1]*(a[i-1]-'a')+mod1)*3+(a[i+m-1]-'a'))%mod1;
val2[i]=((val2[i-1]-treila2[m-1]*(a[i-1]-'a')+mod2)*3+(a[i+m-1]-'a'))%mod2;
if(find(hash1.begin(),hash1.end(),val1[i])!=hash1.end()&&find(hash2.begin(),hash2.end(),val2[i])!=hash2.end())
nrap++;
}
printf("%d",nrap);
fclose(f);
return 0;
}