Pagini recente » Cod sursa (job #304912) | Cod sursa (job #2351854) | Cod sursa (job #2284480) | Cod sursa (job #2615948) | Cod sursa (job #2201071)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define LMAX 2000001
char s1[LMAX], s2[LMAX];
int n1, n2, pi[LMAX];
int v[1000], nr;
void calcPi() {
pi[0] = -1;
int k = -1;
for (int i = 1; i < n1; ++i) {
while (k > -1 && s1[k + 1] != s1[i])
k = pi[k];
if (s1[k + 1] == s1[i])
++k;
pi[i] = k;
}
}
void findOcc() {
int k = -1;
int N1 = n1 - 1;
for (int i = 0; i < n2; ++i) {
while (k > -1 && s1[k + 1] != s2[i])
k = pi[k];
if (s1[k + 1] == s2[i])
++k;
if (k == N1) {
if (nr < 1000)
v[nr] = i - n1 + 1;
++nr;
}
}
}
int main() {
f.getline(s1, LMAX);
f.getline(s2, LMAX);
n1 = strlen(s1);
n2 = strlen(s2);
calcPi();
findOcc();
g << nr << '\n';
if (nr > 1000)
nr = 1000;
for (int i = 0; i < nr; ++i)
g << v[i] << ' ';
g << '\n';
return 0;
}