Pagini recente » Cod sursa (job #2569245) | Cod sursa (job #2382490) | Cod sursa (job #3211632) | Cod sursa (job #41469) | Cod sursa (job #1373343)
#include<fstream>
#include<iostream>
using namespace std;
const int kLMax = 2000005, kSMax = 1010;
char a[kLMax], b[kLMax];
int n, m, q, pi[kLMax];
int sol, poz[kSMax];
void Citire() {
ifstream in ("strmatch.in");
int i;
in.getline(a, kLMax);
in.getline(b, kLMax);
for (i = 0; a[i] >= '0' && a[i] <= 'z'; ++i);
m = i;
for (i = 0; b[i] >= '0' && b[i] <='z'; ++i);
n = i;
for (i = m; i >= 1; --i)
a[i] = a[i-1];
a[0] = ' ';
for (i = n; i >= 1; --i)
b[i] = b[i-1];
b[0] = ' ';
in.close();
}
void Prefix() {
pi[1] = 0;
for (int i = 2; i <= m; ++i) {
while (q && a[q + 1] != a[i])
q = pi[q];
if (a[q + 1] == a[i])
++q;
pi[i] = q;
}
}
void Solve() {
Prefix();
q = 0;
for (int i = 1; i <= n; ++i) {
while (q && a[q+ 1] != b[i])
q = pi[q];
if (a[q + 1] == b[i])
q++;
if(q == m) {
q = pi[m];
++sol;
if (sol <= 1000)
poz[sol] = i - m;
}
}
}
void Afisare() {
ofstream out("strmatch.out");
out << sol << '\n';
sol = min(sol, 1000);
for (int i = 1; i <= sol; ++i)
out << poz[i] << ' ';
out << '\n';
out.close();
}
int main () {
Citire();
Solve();
Afisare();
return 0;
}