Pagini recente » Cod sursa (job #347106) | Cod sursa (job #32823) | Cod sursa (job #2203475) | Cod sursa (job #492008) | Cod sursa (job #2064654)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax = 2000005;
const int K = 256;
const int mod = 101;
char A[NMax], B[NMax];
int vp; // valoarea pattern-ului
void Read()
{
fin >> A;
fin >> B;
}
int Hash_Calcul(char s[])
{
int val = (int)s[0];
int n = strlen(s);
for(int i = 1; i < n; ++i)
{
val = ((val * K + mod)%mod + (int)s[i])%mod;
}
return val;
}
int lgput(int nr, int po)
{
int rez = 1;
do
{
if(po & 1)
rez = (long long)(rez * nr)%mod;
nr = (long long)(nr*nr)%mod;
po = po >> 1;
}while(po);
return rez;
}
int Checking(int i, int j)
{
int ok = 1;
for(int k = i; k < j && ok; ++k)
if(B[k] != A[k-i])
ok = 0;
return ok;
}
char p[NMax];
int matches[NMax];
void Rabin_Karp()
{
vp = Hash_Calcul(A);
int np = strlen(A);
int ns = strlen(B);
int mtch = 0;
int put = lgput(K,np-1);
strncpy(p,B,np);
int rez = Hash_Calcul(p);
if(rez == vp)
{
if(Checking(0, np))
{
++mtch;
matches[mtch] = 0;
}
}
for(int i = np; i < ns; ++i)
{
int a = (int)B[i-np];
rez = (((((rez - (a * put)%mod)%mod) + mod)%mod)*K + (int)B[i])%mod;
if(rez == vp)
{
if(Checking(i-np + 1,i + 1))
{
++mtch;
matches[mtch] = i - np;
if(mtch > 1000)
i = ns;
}
}
}
fout << mtch << "\n";
for(int i=1; i<=min(1000,mtch); ++i)
fout << matches[i] << " ";
}
int main()
{
Read();
Rabin_Karp();
return 0;
}