Pagini recente » Cod sursa (job #3195384) | Cod sursa (job #2612369) | Cod sursa (job #2169577) | Cod sursa (job #1095423) | Cod sursa (job #1969689)
#include <stdint.h>
#include <fstream>
#include <string.h>
#define nmax 10000001
#define mmax 21
using namespace std;
fstream f1("abc2.in", ios::in);
fstream f2("abc2.out", ios::out);
char sir[nmax], cuv[mmax];
const int16_t q=131, d=3;
int16_t m, t[nmax], viz[nmax], pa;
int32_t n, rez;
int16_t maxim()
{
int16_t i, s=1;
for(i=1; i<m; i++)
{
s*=3;
s%=q;
}
return s;
}
int main()
{
f1.getline(sir, nmax);
f1.getline(cuv, mmax);
n=strlen(sir);
m=strlen(cuv);
int32_t i, maxi;
int16_t j, val;
maxi=maxim();///3^(m-1)%q
///construiesti prima secv din textul mare
for(i=0; i<m; i++)
{
if(sir[i]=='a') val=1;
else if(sir[i]=='b') val=2;
else val=3;
t[0]=t[0]*3+val;
t[0]%=q;
}
///retii si celelalte secvente
for(i=1; i<=n-m; i++)
{
if(sir[i-1]=='a') val=1;
else if(sir[i-1]=='b') val=2;
else val=3;
t[i]=(t[i-1]-maxi*val+d*q)%q;
if(sir[i+m-1]=='a') val=1;
else if(sir[i+m-1]=='b') val=2;
else val=3;
t[i]=(t[i]*d+val)%q;
}
///pentru toate cuv din dex
do
{
///creezi patternul curent
pa=0;
for(j=0; j<m; j++)
{
if(cuv[j]=='a') val=1;
else if(cuv[j]=='b') val=2;
else val=3;
pa=pa*3+val;
pa%=q;
}
///il cauti in textul mare si il marchezi daca il gasesti
for(i=0; i<n-m; i++)
if(t[i]==pa)
{
///cauta
int16_t ok=1;
for(j=0; j<m; j++)
if(sir[i+j]!=cuv[j]) {ok=0; break;}
if((ok)&&(!viz[i]))
{
viz[i]=1;
rez++;
}
}
}
while(f1>>cuv);
f2<<rez;
return 0;
}