Pagini recente » Profil Vasiidan12 | Diferente pentru agm-2018/runda1 intre reviziile 20 si 14 | Atasamentele paginii prolotomiada1 | Cod sursa (job #2841491) | Cod sursa (job #1505145)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MOD 2159041
using namespace std;
int lungime,lim;
unsigned int put[20];
vector<unsigned int>b[MOD];
char ch1[10000004],ch2[25];
int ct=0;
void findit(unsigned int a)
{
int key=a%MOD;
vector<unsigned int>::iterator it;
for(it=b[key].begin();it!=b[key].end();++it)
{
if(*it==a)
{
ct++;
return;
}
}
}
int main()
{
freopen ("abc2.in","r",stdin);
freopen ("abc2.out","w",stdout);
scanf("%s",ch1);
scanf("%s",ch2);
lungime=strlen(ch2);
lim=strlen(ch1);
put[0]=1;
for(int i=1;i<20;i++) put[i]=put[i-1]*3;
unsigned int h1=0;
while(1)
{
h1=0;
for(int i=0;i<lungime;i++) h1+=(ch2[i]-'a')*put[lungime-1-i];
b[h1%MOD].push_back(h1);
scanf("%s",ch2);
if(feof(stdin)) break;
}
h1=0;
for(int i=0;i<lungime;i++) h1+=(ch1[i]-'a')*put[lungime-1-i];
findit(h1);
for(int i=lungime;i<lim;i++)
{
h1-=((ch1[i-lungime]-'a')*put[lungime-1]);
h1*=3;
h1+=(ch1[i]-'a');
findit(h1);
}
printf("%d\n",ct);
}