Pagini recente » Cod sursa (job #2057763) | Cod sursa (job #1322259) | Cod sursa (job #1733181) | Cod sursa (job #169145) | Cod sursa (job #2376940)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
#define pb push_back
using namespace std;
const int MAXSIZE = 2e6, MAXN = 1e3;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lengths[MAXSIZE + 10], solutions[MAXN + 10], solutionsNr, n, m;
char prefix[MAXSIZE + 10], str[MAXSIZE + 10];
void read() {
fin.get(prefix, MAXSIZE + 10);
fin.get();
fin.get(str, MAXSIZE + 10);
m = strlen(prefix);
n = strlen(str);
}
void preprocess() {
for (int i = 1, j = 0; i < m;) {
if (prefix[i] == prefix[j])
lengths[i++] = ++j;
else if (!j)
i++;
else
j = lengths[j - 1];
}
}
void solve() {
for (int i = 0, j = 0; i < n;) {
if (str[i] == prefix[j]) {
i++, j++;
if (j == m) {
solutionsNr++;
if (solutionsNr <= MAXN)
solutions[solutionsNr] = i - j;
j = lengths[j - 1];
}
}
else if (!j)
i++;
else
j = lengths[j - 1];
}
}
void print() {
fout << solutionsNr << "\n";
for (int i = 1; i <= min(solutionsNr, MAXN); ++i)
fout << solutions[i] << " ";
}
int main() {
read();
preprocess();
solve();
print();
return 0;
}