Pagini recente » Cod sursa (job #2906175) | Cod sursa (job #2261860) | Cod sursa (job #1344724) | Cod sursa (job #1966420) | Cod sursa (job #1423343)
#include<fstream>
#include<string>
#include<vector>
#include<cstring>
#define NMAX 2000010
#define base 67
#define MOD1 104729
#define MOD2 666013
using namespace std;
string A, B;
vector<int> sol;
long long hA1, hA2, hB1, hB2, base_pow1, base_pow2, potriviri_suplimentare=0;
inline bool egale()
{
if (hA1==hB1 && hA2==hB2) return true;
return false;
}
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';
}
long long compute(string S, int st, int dr, long long MOD)
{
long long rez=0;
for (int i=st; i<dr; ++i)
{
rez=(rez*base+valoare(S[i]))%MOD;
}
return rez;
}
long long putere(int N, long long MOD)
{
long long 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;
base_pow1=putere(A.length()-1, MOD1);
base_pow2=putere(A.length()-1, MOD2);
hA1=compute(A, 0, A.length(), MOD1);
hA2=compute(A, 0, A.length(), MOD2);
hB1=compute(B, 0, A.length(), MOD1);
hB2=compute(B, 0, A.length(), MOD2);
if (egale())
{
sol.push_back(0);
}
for (int i=A.length(); i<B.length(); ++i)
{
hB1=hB1-(base_pow1*valoare(B[i-A.length()]))%MOD1;
if (hB1<0) hB1+=MOD1;
hB1=(hB1*base+valoare(B[i]))%MOD1;
hB2=hB2-(base_pow2*valoare(B[i-A.length()]))%MOD2;
if (hB2<0) hB2+=MOD2;
hB2=(hB2*base+valoare(B[i]))%MOD2;
if (egale())
{
if (sol.size()<1000) sol.push_back(i-A.length()+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;
}