Pagini recente » Cod sursa (job #300166) | Cod sursa (job #2712159) | Cod sursa (job #794651) | Cod sursa (job #873923) | Cod sursa (job #2156339)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
vector<int> Zfunction(string s) {
int n = s.size();
vector<int> z(n);
int L = 0, R = 0;
for (int i = 1; i < n; i++) {
if (i > R) {
L = R = i;
while (R < n && s[R-L] == s[R]) R++;
z[i] = R-L; R--;
} else {
int k = i-L;
if (z[k] < R-i+1) z[i] = z[k];
else {
L = i;
while (R < n && s[R-L] == s[R]) R++;
z[i] = R-L; R--;
}
}
}
return z;
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
fin >> a >> b;
b = a + "$" + b;
vector<int> z = Zfunction(b);
vector<int> ap;
for (int i = 1; i < (int) b.size(); ++i) {
if (z[i] == (int) a.size()) {
ap.push_back(i - a.size());
}
}
fout << ap.size() << '\n';
ap.resize(min((int) ap.size(), 1000));
for (int x: ap) {
fout << x - 1 << ' ';
}
fout << '\n';
}