Pagini recente » Istoria paginii utilizator/salagean_briana | Cod sursa (job #2073061) | Cod sursa (job #2176927) | Cod sursa (job #519837) | Cod sursa (job #1423366)
#include<fstream>
#include<string>
#include<vector>
#include<cstring>
#define NMAX 2000010
#define base 67
#define MOD1 104729
#define MOD2 666013
#define egale hA1==hB1 && hA2==hB2
using namespace std;
char A[NMAX], B[NMAX];
vector<int> sol;
long long hA1, hA2, hB1, hB2, base_pow1, base_pow2, potriviri_suplimentare=0;
inline long long valoare(char c)
{
if (c>='A' && c<='Z') return c-'A';
if (c>='a' && c<='z') return 'z'-'a'+c-'a';
return ('z'-'a')*2+c-'0';
}
void compute(int lim)
{
for (int i=0; i<lim; ++i)
{
hA1=(hA1*base+valoare(A[i]))%MOD1;
hA2=(hA1*base+valoare(A[i]))%MOD2;
hB1=(hB1*base+valoare(B[i]))%MOD1;
hB2=(hB2*base+valoare(B[i]))%MOD2;
}
}
void putere(int N)
{
base_pow1=base_pow2=1;
for (int i=1; i<=N; ++i)
{
base_pow1=(base_pow1*base)%MOD1;
base_pow2=(base_pow2*base)%MOD2;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>A>>B;
int lgA=strlen(A), lgB=strlen(B);
putere(lgA-1);
compute(lgA);
if (egale)
{
sol.push_back(0);
}
for (int i=lgA; i<lgB; ++i)
{
hB1=hB1-(base_pow1*valoare(B[i-lgA]))%MOD1;
if (hB1<0) hB1+=MOD1;
hB1=(hB1*base+valoare(B[i]))%MOD1;
hB2=hB2-(base_pow2*valoare(B[i-lgA]))%MOD2;
if (hB2<0) hB2+=MOD2;
hB2=(hB2*base+valoare(B[i]))%MOD2;
if (egale)
{
if (sol.size()<1000) sol.push_back(i-lgA+1);
else ++potriviri_suplimentare;
}
}
g<<sol.size()+potriviri_suplimentare<<"\n";
for (int i=0; i<sol.size(); ++i)
g<<sol[i]<<" ";
g<<"\n";
return 0;
}