Pagini recente » Cod sursa (job #1065638) | Cod sursa (job #2186140) | Cod sursa (job #2883313) | Cod sursa (job #876948) | Cod sursa (job #3041428)
#include <bits/stdc++.h>
#define GARDA fin.close(); fout.close(); exit(0);
using namespace std;
string const& task("strmatch");
ifstream fin(task + ".in");
ofstream fout(task + ".out");
int const N(2e6 + 5), K(1000);
char A[N], B[N], s[2 * N];
int pi[2 * N], a, b, n, res[K + 1], cnt;
inline void Pi() {
int j = 0;
for (int i = 2; i <= n; ++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 >> B;
a = static_cast<int>(strlen(A));
b = static_cast<int>(strlen(B));
for (int i = 0; i < a; ++i)
s[++n] = A[i];
s[++n] = '$';
for (int i = 0; i < b; ++i)
s[++n] = B[i];
Pi();
for (int i = a + 2; i <= n; ++i) {
if (pi[i] != a)
continue;
++cnt;
if (cnt <= K)
res[cnt] = i - 2 * a - 1;
}
fout << cnt << '\n';
for (int i = 1; i <= min(cnt, K); ++i)
fout << res[i] << ' ';
GARDA
}