Pagini recente » Cod sursa (job #302026) | Cod sursa (job #2377870) | Cod sursa (job #2707855) | Cod sursa (job #3003531) | Cod sursa (job #2352094)
#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 pre1[SMAX];
int pre2[SMAX];
int nrSol;
int sol[SMAX];
int main() {
fin >> a; m = strlen(a);
fin >> b; n = strlen(b);
int k = 0;
for (int i = 1; i < m; i++) {
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++) {
while (a[k] != b[i] && k)
k = pre1[k - 1];
if (a[k] == b[i])
k++;
pre2[i] = k;
if (k == m)
sol[nrSol++] = i - m + 1;
}
fout << nrSol << '\n';
for (int i = 0; i < nrSol && i < MAX; i++)
fout << sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}