Pagini recente » Cod sursa (job #2004182) | Cod sursa (job #2261443) | Cod sursa (job #583987) | Cod sursa (job #2321489) | Cod sursa (job #2372856)
#include <fstream>
#include <cstring>
using namespace std;
char a[2000005];
char b[2000005];
int p[2000005];
int m;
void form_prefix() {
m = strlen(a+1);
int i = 0;
p[1] = 0;
for (int j = 2; j <= m; ++j) {
while (i > 0 && a[i+1] != a[j])
i = p[i];
if (a[i+1] == a[j])
++i;
p[j] = i;
}
}
int n, nr;
int afis[1005];
void str_matching() {
int n = strlen(b+1);
int k = 0;
for (int i = 1; i <= n; ++i) {
while (k != 0 && b[i] != a[k+1])
k = p[k];
if (b[i] == a[k+1])
k++;
if (k == m) {
nr++;
if (nr <= 1000)
afis[nr] = i - m;
k = p[k];
}
}
}
int main() {
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in.getline(a+1, 2000005);
in.get(b+1, 2000005);
form_prefix();
str_matching();
int aa = nr;
out << aa << '\n';
if (aa > 1000) aa = 1000;
for (int i = 1; i <= aa; ++i)
out << afis[i] << " ";
return 0;
}