Pagini recente » Cod sursa (job #1533028) | Cod sursa (job #18375) | Cod sursa (job #572168) | Cod sursa (job #1288957) | Cod sursa (job #886874)
Cod sursa(job #886874)
# include <algorithm>
# include <fstream>
# include <vector>
using namespace std;
string A, B;
int N, M, solution, Z[4000005];
vector <int> sol;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
inline void z_alg (int *Z, string sir) {
for (int i = 1, L = 0, R = 0; i < N + M; ++i)
if (i > R) {
for (L = R = i; R < N + M && sir[R - L] == sir[R]; ++R);
Z[i] = R-- - L;
} else {
if (Z[i - L] < R - i + 1) Z[i] = Z[i - L];
else {
for (L = i; R < N + M && sir[R - L] == sir[R]; ++R);
Z[i] = R-- - L;
}
}
}
int main (void) {
f >> A >> B;
N = A.size (), M = B.size ();
z_alg (Z, A + B);
for (int i = 0; i < N + M; ++i)
if (Z[i] == N)
if (++solution <= 1000) sol.push_back (i - N);
g << solution << "\n";
for (vector <int> :: iterator it = sol.begin (); it != sol.end (); ++it)
g << *it << " ";
}