Pagini recente » Cod sursa (job #1066167) | Cod sursa (job #856909) | Cod sursa (job #2376630) | Cod sursa (job #520311) | Cod sursa (job #2417677)
#include <bits/stdc++.h>
#define lld long long
#define mod 10007
using namespace std;
FILE *fin=fopen("abc2.in","r");
FILE *fout=fopen("abc2.out","w");
class lst
{
private:
struct nod
{
nod *urm;
unsigned int value;
nod(unsigned int v)
{
urm = 0;
value = v;
}
nod()
{
value = 0;
urm = NULL;
}
};
nod *root;
public:
lst()
{
root = 0;
}
void add(unsigned int v)
{
nod *nw = new nod(v);
if (!root)
{
root = nw;
return;
}
nw -> urm = root;
root = nw;
}
bool exists(unsigned int v)
{
if (!root) return false;
nod *act = root;
while (act)
{
if(act->value == v) return true;
act = act->urm;
}
return false;
}
};
lst dispersionTable[mod+1];
char s[10000005], p[25];
int ln,lp, ans;
unsigned int wh;
unsigned int hsh, pw[25];
const unsigned int pww = 3;
void add()
{
wh = hsh % mod;
if (!dispersionTable[wh].exists(hsh))
dispersionTable[wh].add(hsh);
}
bool findd()
{
wh = hsh % mod;
return dispersionTable[wh].exists(hsh);
}
int main()
{
//freopen("abc2.in","r",stdin);
//freopen("abc2.out","w",stdout);
fscanf(fin,"%s\n", s);
pw[0] = 1;
for (int i=1; i<20; ++i)
pw[i] = pw[i-1] * pww;
fscanf(fin,"%s\n",p);
lp = strlen(p);
do
{
hsh = 0;
for (int i=lp-1; i>=0; --i)
hsh = hsh + (p[i]-'a')*pw[lp-i-1];
add();
}
while (fscanf(fin,"%s\n",p)!=EOF);
hsh = 0;
for (int i=lp-1; i>=0; --i)
{
s[i]-='a';
hsh = hsh + s[i]*pw[lp-i-1];
}
if (findd())++ans;
for (int i=lp; s[i]; ++i)
{
s[i]-='a';
hsh = (hsh - s[i-lp]*pw[lp-1]) *pww + s[i];
if (findd())++ans;
}
fprintf(fout,"%d\n",ans);
fclose(fin);
fclose(fout);
return 0;
}