Pagini recente » Cod sursa (job #2334206) | Cod sursa (job #2796196) | Cod sursa (job #1424604) | Cod sursa (job #1474783) | Cod sursa (job #1289974)
#include <fstream>
#include <vector>
using namespace std;
#define q 101
#define M1 666013
#define M2 10007
vector<int> Sol;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,B;
fin >> A >> B;
int n = A.size();
int m = B.size();
if(n > m)
{
fout << "0";
return 0;
}
int Hpat1 = 0, Hpat2 = 0;
int Hstr1 = 0, Hstr2 = 0;
for(int i = 0; i < n; i++)
{
Hpat1 = (Hpat1 * q + A[i]) % M1;
Hpat2 = (Hpat2 * q + A[i]) % M2;
Hstr1 = (Hstr1 * q + B[i]) % M1;
Hstr2 = (Hstr2 * q + B[i]) % M2;
}
int q1n = 1, q2n = 1;
for(int i = 1; i < n; i++)
{
q1n = q1n * q % M1;
q2n = q2n * q % M2;
}
if(Hpat1 == Hstr1 && Hpat2 == Hstr2)
Sol.push_back(0);
int Nr = Sol.size();
for(int i = n; i < m; i++)
{
Hstr1 =((Hstr1 - (q1n * B[i-n]) % M1 + M1) * q + B[i]) % M1;
Hstr2 =((Hstr2 - (q2n * B[i-n]) % M2 + M2) * q + B[i]) % M2;
if(Hstr1 == Hpat1 && Hstr2 == Hpat2)
{
Nr++;
if(Nr < 1000) Sol.push_back(i-n+1);
}
}
fout << Nr << "\n";
for(int i = 0; i < Sol.size(); i++)
{
fout << Sol[i] << " ";
}
}