Pagini recente » Cod sursa (job #15405) | Cod sursa (job #464698) | Cod sursa (job #939971) | Cod sursa (job #2933762) | Cod sursa (job #1423383)
#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;
string A, B;
vector<int> sol;
int hA1, hA2, hB1, hB2, base_pow1, base_pow2, potriviri_suplimentare=0;
inline int 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';
}
int compute(string S, int st, int dr, int MOD)
{
int rez=0;
for (int i=st; i<dr; ++i)
{
rez=(rez*base+valoare(S[i]))%MOD;
}
return rez;
}
int putere(int N, int MOD)
{
int rez=1;
for (int i=1; i<=N; ++i)
{
rez=(rez*base)%MOD;
}
return rez;
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>A>>B;
int lgA=A.length(), lgB=B.length();
base_pow1=putere(lgA-1, MOD1);
base_pow2=putere(lgA-1, MOD2);
hA1=compute(A, 0, lgA, MOD1);
hA2=compute(A, 0, lgA, MOD2);
hB1=compute(B, 0, lgA, MOD1);
hB2=compute(B, 0, lgA, MOD2);
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;
}