Pagini recente » Cod sursa (job #3217861) | Cod sursa (job #764452) | Cod sursa (job #218998) | Cod sursa (job #1802473) | Cod sursa (job #2748650)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
/// Z Algorithm
const int LMAX = 2000000;
string a;
string b;
string sir;
int zBox[1 + 2 * LMAX];
int nrSol;
vector<int> sol;
void zAlgorithm()
{
int st = 0;
int dr = 0;
for (int i = 1; i < sir.size(); i++)
{
if (i <= dr)
{
zBox[i] = min(zBox[i - st], dr - i + 1);
}
while (i + zBox[i] < sir.size() && sir[i + zBox[i]] == sir[zBox[i]])
{
zBox[i]++;
}
if (i + zBox[i] - 1 > dr)
{
st = i;
dr = i + zBox[i] - 1;
}
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> a >> b;
sir = a + '$' + b;
zAlgorithm();
for (int i = a.size() + 1; i + a.size() - 1 < sir.size(); i++)
{
if (zBox[i] == a.size())
{
nrSol++;
if (nrSol <= 1000)
{
sol.push_back(i - a.size() - 1);
}
}
}
out << nrSol << '\n';
for (int i = 0; i < sol.size(); i++)
{
out << sol[i] << ' ';
}
return 0;
}