Pagini recente » Cod sursa (job #852384) | Cod sursa (job #3153046) | Cod sursa (job #354300) | Cod sursa (job #1126818) | Cod sursa (job #749114)
Cod sursa(job #749114)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned int uint;
const int mod=5003;
char l[10000010],ch[30];
unsigned int v[50001];
vector <uint> h[mod];
bool fct(uint x, bool ok){
uint aux;
aux=x%mod;
for (vector <uint>::iterator it=h[aux].begin(); it!=h[aux].end(); ++it){
if (*it==x){
return 1;
}
}
if (ok){
h[aux].push_back(x);
}
return 0;
}
int main()
{
unsigned int m,n,i,j,aux,sol=0,x=0;
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
l[0]=' ';
fgets(l+1,10000005,stdin);
n=strlen(l)-2;
fgets(ch,25,stdin);
m=strlen(ch)-1;
for (i=0;i<m;++i)
v[1]=v[1]*3+ch[i]-'a';
fct(v[1], 1);
i=1;
while (!feof(stdin))
{
++i;
fgets(ch,25,stdin);
for (j=0;j<m;++j)
v[i]=v[i]*3+ch[j]-'a';
fct(v[i], 1);
fprintf(stderr, "%u ", v[i]);
}
for (aux=1,i=1;i<m;++i)
{
aux*=3;
x=x*3+l[i]-'a';
}
fprintf(stderr, "\n\n%u %u\n\n", aux, x);
for (j=1;j<=n-m+1;++j)
{
x=(x-(x/aux)*aux)*3+l[j+m-1]-'a';
if (fct(x, 0))
++sol;
fprintf(stderr, "%u, %u: %u\n", j, x, sol);
}
printf("%u\n",sol);
return 0;
}