Mai intai trebuie sa te autentifici.
Cod sursa(job #1984443)
Utilizator | Data | 24 mai 2017 20:57:57 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.48 kb |
#include <fstream>
#include <vector>
#define MOD 666013
#define MOD2 30103
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int LP, LT, i, j, nr;
int NRP, NRT, Prod;
int NRP2, NRT2, Prod2;
vector <int> SOL;
vector <int> :: iterator it;
string P, T;
int main()
{
fin >> P >> T;
LP=P.size();
LT=T.size();
Prod=1;
Prod2=1;
for (i=LP-1; i>=0; i--)
{
NRP+=Prod*(P[i]);
NRP%=MOD;
NRT+=Prod*(T[i]);
NRT%=MOD;
if (i!=0)
{
Prod*=199;
Prod%=MOD;
}
NRP2+=Prod2*(P[i]);
NRP2%=MOD2;
NRT2+=Prod2*(T[i]);
NRT2%=MOD2;
if (i!=0)
{
Prod2*=199;
Prod2%=MOD2;
}
}
if (NRT==NRP && NRT2==NRP2)
SOL.push_back(0);
for (i=LP; i<LT; i++)
{
nr=Prod*(T[i-LP]);
nr%=MOD;
NRT-=nr;
if (NRT<0)
NRT+=MOD;
NRT*=199;
NRT%=MOD;
NRT+=T[i];
if (NRT>=MOD)
NRT-=MOD;
nr=Prod2*(T[i-LP]);
nr%=MOD2;
NRT2-=nr;
if (NRT2<0)
NRT2+=MOD2;
NRT2*=199;
NRT2%=MOD2;
NRT2+=T[i];
if (NRT2>=MOD2)
NRT2-=MOD2;
if (NRT==NRP && NRT2==NRP2)
SOL.push_back(i-LP+1);
}
fout << SOL.size() << '\n';
int K=SOL.size();
for (i=0; i<min(K, 1000); i++)
fout << SOL[i] << " ";
fin.close();
fout.close();
return 0;
}