Pagini recente » Cod sursa (job #1909302) | Cod sursa (job #975844) | Cod sursa (job #1836673) | Cod sursa (job #524424) | Cod sursa (job #1283974)
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void zAlgorithm(const string& s, const size_t sz, vector<size_t>& shifts)
{
vector<size_t> z(s.size(), 0);
size_t L = 0, R = 0;
z[0] = s.size();
for (size_t i = 1; i < s.size(); ++i)
{
//Find new interval [L, R]
if (i > R)
{
L = R = i;
while (R < s.size() && s[R] == s[R - L])
++R;
--R; //because R will be bigger by 1
z[i] = R - L + 1;
}
else
{
size_t k = i - L;
if (z[k] < R - i + 1)
z[i] = z[k];
else //R is already bigger than i
{
L = i;
while (R < s.size() && s[R] == s[R - L])
++R;
--R;
z[i] = R - L + 1;
}
}
}
for (size_t i = 0; i < z.size(); ++i)
if (z[i] == sz)
shifts.push_back(i - sz - 1);
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, t, s;
fin >> p >> t;
s = p + '$' + t;
vector<size_t> shifts;
zAlgorithm(s, p.size(), shifts);
fout << shifts.size() << '\n';
for (size_t i = 0; i < min(shifts.size(), size_t(1000)); ++i)
fout << shifts[i] << ' ';
fout << '\n';
return 0;
}