Pagini recente » Cod sursa (job #2952982) | Cod sursa (job #553075) | Cod sursa (job #1707499) | Cod sursa (job #685374) | Cod sursa (job #1691513)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int prf[100010];
vector<int> pozitii;
char * s;
char * d;
void prefix();
int search();
int main() {
ifstream in("strmach.in");
s = new char[2000010];
d = new char[2000010];
in >> s + 1 >> d;
ofstream out("strmach.out");
out << search() << '\n';
for (auto i : pozitii)
out << i << ' ';
in.close();
out.close();
return 0;
}
int search() {
int r = 0;
prefix();
s++;
int n = strlen(s);
int m = strlen(d);
int i = 0;
int k = 0;
while (i <= m) {
if (k == -1) {
i++;
k = 0;
}
else {
if (d[i] == s[k]) {
k++;
i++;
if (k == n) {
if (pozitii.size() < 1000)
pozitii.push_back(i - k);
r++;
k = prf[k];
}
}
else
k = prf[k];
}
}
return r;
}
void prefix() {
int l = strlen(s);
prf[0] = -1;
int k;
for (int i = 1; i < l; i++) {
k = prf[i - 1];
while (k >= 0 && s[k + 1] != s[i])
k = prf[k];
prf[i] = k + 1;
}
}