Pagini recente » Cod sursa (job #1846724) | Cod sursa (job #562457) | Cod sursa (job #1755213) | Cod sursa (job #1274624) | Cod sursa (job #2194664)
#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 >> A >> B;
n = strlen(A);
m = strlen(B);
if (n > m) return !(cout << 0);
for (int i = 1; i < n; i++) {
while (k && A[k] != A[i])
k = prefix[k - 1];
if (A[k] == A[i])
k++;
prefix[i] = k;
}
k = 0;
for (int i = 0; i < m; i++) {
while (k && A[k] != B[i])
k = prefix[k - 1];
if (A[k] == B[i])
k++;
if (k == n) {
if (solution.size() <= 1000)
solution.push_back(i - n + 1);
k = prefix[k - 1];
}
}
fout << solution.size() << "\n";
for (int i = 0; i < solution.size(); i++)
fout << solution[i] << " ";
}