Pagini recente » Cod sursa (job #2845535) | Cod sursa (job #2538567) | Cod sursa (job #3199294) | Profil BlackNesta | Cod sursa (job #1763112)
#include <cstdio>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define N 4000100
vector<int> sol;
string a, b, s;
int z[N], n, k;
int main() {
f >> a >> b;
string s = "0";
s += a;
s += '#';
s += b;
n = s.length() - 1;
k = 1; // numarul pt care k + z[k] - 1 e maxim
for (int i = 2; i <= n; ++i) {
if (k + z[k] - 1 < i) {
int p = i;
for (int j = 1; p <= n && s[p] == s[j]; ++p, ++j);
z[i] = p - i;
k = i;
} else {
z[i] = min(z[i - k + 1], k + z[k] - 1 - (i - 1));
for (;z[i] + i <= n && s[z[i] + i] == s[z[i] + 1]; ++z[i]);
if (i + z[i] - 1 > k + z[k] - 1) {
k = i;
}
}
}
for (int i = a.length() + 1; i <= n; ++i) {
if (z[i] >= a.length()) {
sol.push_back(i - a.length() - 2);
}
}
g << sol.size() << "\n";
for (int i = 0; i < min((int)sol.size(), 1000); ++i) {
g << sol[i] << " ";
}
return 0;
}