Pagini recente » Cod sursa (job #1518496) | Cod sursa (job #311707) | Cod sursa (job #932537) | Cod sursa (job #799321) | Cod sursa (job #2194673)
#include <bits/stdc++.h>
#define Nmax 2000006
using namespace std;
char A[Nmax], B[Nmax];
int prefix[Nmax], k, n, m, nrsol;
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) {
nrsol++;
if (solution.size() < 1000)
solution.push_back(i - m + 1);
k = prefix[k - 1];
}
}
fout << nrsol << "\n";
for (int i = 0; i < solution.size(); i++)
fout << solution[i] << " ";
}