Pagini recente » Cod sursa (job #1055570) | Cod sursa (job #1080139) | Cod sursa (job #2384503) | Cod sursa (job #675051) | Cod sursa (job #1976879)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000002
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[NMAX];
char A[NMAX], B[NMAX];
void prefix(const int N) {
int k = 0;
for (int i = 2; i <= N; ++i) {
while (k > 0 && A[k + 1] != A[i])
k = pi[k];
if (A[k + 1] == A[i])
k++;
pi[i] = k;
}
}
void match(const int N, const int M) {
vector<int> poz;
int k = 0, nrMatches = 0;
for (int i = 1; i <= M; ++i) {
while (k > 0 && A[k + 1] != B[i])
k = pi[k];
if (A[k + 1] == B[i])
k++;
if (k == N) {
nrMatches++;
if (nrMatches <= 1000)
poz.push_back(i - N);
}
}
fout << nrMatches << "\n";
for (auto val: poz)
fout << val << " ";
}
int main() {
fin >> (A + 1) >> (B + 1);
int N = strlen(A + 1);
int M = strlen(B + 1);
if (N > M) {
fout << 0;
return 0;
}
prefix(N);
match(N, M);
return 0;
}