Pagini recente » Cod sursa (job #2379568) | Cod sursa (job #3286092) | Cod sursa (job #1545519) | Cod sursa (job #2922063) | Cod sursa (job #1763095)
#include <cstdio>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define N 2000100
vector<int> sol;
string a, b, s;
int z[N], n, k;
int main() {
f >> a >> b;
string s = "0";
for (int i = 0; i < a.length(); ++i) {
s += a[i];
}
s += '#';
for (int i = 0; i < b.length(); ++i) {
s += b[i];
}
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] = z[i - k + 1];
if (z[i] + i - 1 > k + z[k] - 1) {
z[i] = z[k] + k - 1 - (i - 1);
}
for (;z[i] + i <= n && s[z[i] + i] == s[z[i] + 1]; ++z[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;
}