Pagini recente » Cod sursa (job #2051198) | Cod sursa (job #155355) | Cod sursa (job #1384416) | Cod sursa (job #1794045) | Cod sursa (job #2494850)
#include <cstring>
#include <iostream>
#include <fstream>
#include <set>
#define NMAX 1000
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char T[NMAX], P[NMAX];
int n,m;
set<int> S;
unsigned long putere(int d, int m)
{
int i;
unsigned long p=1;
for(i=1; i<m; ++i)
p*=d;
return p;
}
int EQ(char *P, char *T, int k)
{
int i;
for(i=0; i<m; ++i)
if(P[i]!=T[k+i])
return 0;
return 1;
}
void RabinKarp( char *T, char *P, int d, int q)
{
unsigned long h, p, t0;
int ct=0;
n = strlen(T);
m = strlen(P);
h = putere(d,m)%q;
p = t0 = 0;
for(int i=0; i<m; ++i) //calculez p si t0 initial
{
p = (d*p + P[i])%q;
t0 = (d*t0 + T[i])%q;
}
for(int k=0; k<=n-m; ++k) //incerc toate posibilele deplasamente
{
if(p==t0)
if( EQ(P,T,k)) // am gasit la pozitia k
S.insert(k);
t0 = (t0 + d*q - T[k]*h)%q; //recalculez t0
t0 = (t0*d + T[k+m])%q;
}
}
int main()
{
int poz;
fin>>T;
int ct=0;
while(fin>>P)
{
RabinKarp(T,P,128,131);
}
fout<<S.size();
return 0;
}