Pagini recente » Cod sursa (job #1948453) | Cod sursa (job #3185224) | Cod sursa (job #2755888) | Cod sursa (job #271422) | Cod sursa (job #2194668)
#include <bits/stdc++.h>
#define Nmax 2000006
using namespace std;
char A[Nmax], B[Nmax];
int prefix[Nmax], k, n, m;
vector <int> solution;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
fin >> B >> A;
m = strlen(B);
n = strlen(A);
for (int i = 1; i < m; i++) {
while (k && B[k] != B[i])
k = prefix[k - 1];
if (B[k] == B[i])
k++;
prefix[i] = k;
}
k = 0;
for (int i = 0; i < n; i++) {
while (k && B[k] != A[i])
k = prefix[k - 1];
if (B[k] == A[i])
k++;
if (k == m) {
if (solution.size() <= 1000)
solution.push_back(i - m + 1);
k = prefix[k - 1];
}
}
fout << solution.size() << "\n";
for (int i = 0; i < solution.size(); i++)
fout << solution[i] << " ";
}