Pagini recente » Cod sursa (job #3270774) | Istoria paginii runda/tema_1_10f | Cod sursa (job #746385) | Cod sursa (job #1123490) | Cod sursa (job #2352050)
#include <cstring>
#include <fstream>
#define MAX 1000
#define SMAX 2000010
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
int m; char a[SMAX];
int n; char b[SMAX];
int k;
int pre1[SMAX];
int pre2[SMAX];
int nrSol;
int sol[SMAX];
int main() {
fin >> a; m = strlen(a);
fin >> b; n = strlen(b);
for (int i = 1; i < m; i++)
if (a[k] == a[i])
pre1[i] = ++k;
else {
while (a[k] != a[i] && k)
k = pre1[k - 1];
if (a[k] == a[i])
k++;
pre1[i] = k;
}
k = 0;
for (int i = 0; i < n; i++)
if (a[k] == b[i]) {
pre2[i] = ++k;
if (k == m)
sol[nrSol++] = i - m + 1;
}
else {
while (a[k] != b[i] && k)
k = pre1[k - 1];
if (a[k] == b[i])
k++;
pre2[i] = k;
}
fout << nrSol << '\n';
for (int i = 0; i < nrSol && i < MAX; i++)
fout << sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}