Pagini recente » Cod sursa (job #2100012) | Cod sursa (job #3209865) | Cod sursa (job #2590236) | Cod sursa (job #3238956) | Cod sursa (job #2194672)
#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.getline(B, Nmax);
fin.getline(A, Nmax);
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] << " ";
}