Pagini recente » Cod sursa (job #177544) | Cod sursa (job #839897) | Cod sursa (job #1683051) | Cod sursa (job #2959628) | Cod sursa (job #1976892)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000002
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2 * NMAX];
int Z[2 * NMAX];
void Zalgo(const int N, const int start) {
Z[0] = N;
int st = 0, dr = 0;
for (int i = 1; i < N; ++i) {
if (i > dr) {
st = dr = i;
while (dr < N && A[dr] == A[dr - i])
dr++;
Z[i] = dr - i;
dr--;
}
else {
int k = i - st;
if (Z[k] < dr - i + 1)
Z[i] = Z[k];
else {
st = i;
while (dr < N && A[dr] == A[dr - i])
dr++;
Z[i] = dr - i;
dr--;
}
}
}
vector<int> poz;
int nrMatches = 0;
for (int i = start; i < N; ++i) {
if (Z[i] == start - 1) {
nrMatches++;
if (nrMatches <= 1000)
poz.push_back(i - start);
}
}
fout << nrMatches << "\n";
for (auto val: poz)
fout << val << " ";
}
int main() {
fin >> A;
int N = strlen(A);
A[N] = '#';
A[N + 1] = 0;
int start = N + 1;
fin >> (A + N + 1);
N = strlen(A);
Zalgo(N, start);
return 0;
}