Pagini recente » Cod sursa (job #1188830) | Cod sursa (job #311724) | Cod sursa (job #2306943) | Cod sursa (job #1108039) | Cod sursa (job #2776307)
#include <iostream>
#include <fstream>
#include <string>
#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl
const int NMAX = 2e6;
int z[2 + 2 * NMAX];
std::string a, b;
int cnt = 0;
int sol[1000];
int main() {
inout("strmatch");
in >> a >> b;
int target = a.size();
a = a + "." + b; // ABA.CABBCABABAB
int left = 0, right = 0;
for (int i = 1; i < a.size(); ++i) {
if (i > right) {
left = right = i;
while (right < a.size() && a[right - left] == a[right])
++right;
z[i] = right - left;
--right;
}
else {
int _i = i - left;
if (z[_i] < right - i + 1)
z[i] = z[_i];
else {
left = i;
while (right < a.size() && a[right - left] == a[right])
++right;
z[i] = right - left;
--right;
}
}
}
for (int i = 1; i < a.size(); ++i) {
if (z[i] == target) {
if (cnt < 1000)
sol[cnt] = i - target - 1;
++cnt;
}
}
out << cnt << '\n';
for (int i = 0; i < std::min(1000, cnt); ++i)
out << sol[i] << ' ';
out << '\n';
return 0;
}