Pagini recente » Cod sursa (job #695675) | Cod sursa (job #568585) | Cod sursa (job #2730756) | Cod sursa (job #2594338) | Cod sursa (job #2881717)
#include <bits/stdc++.h>
using namespace std;
string const& task("strmatch");
ifstream fin(task + ".in");
ofstream fout(task + ".out");
int const N(2e6 + 5);
char A[N], B[N], S[2 * N];
int a, b, s, pi[2 * N];
void PF() {
int j = 0;
for (int i = 2; i <= s; ++i) {
while (j && S[i] != S[j + 1])
j = pi[j];
if (S[i] == S[j + 1]) ++j;
pi[i] = j;
}
}
signed main() {
fin >> (A + 1) >> (B + 1);
a = static_cast<int>(strlen(A + 1));
b = static_cast<int>(strlen(B + 1));
for (int i = 1; i <= a; ++i)
S[++s] = A[i];
S[++s] = '$';
for (int i = 1; i <= b; ++i)
S[++s] = B[i];
PF();
int res = 0;
for (int i = a + 2; i <= s; ++i)
if (pi[i] == a)
++res;
fout << res << '\n';
res = min(res, 1000);
for (int i = a + 2; i <= s; ++i)
if (pi[i] == a) {
fout << i - 2 * a - 1 << ' ';
if (--res == 0) break;
}
return 0;
}