Pagini recente » Cod sursa (job #547404) | Cod sursa (job #845610) | Cod sursa (job #823899) | Cod sursa (job #2665460) | Cod sursa (job #935494)
Cod sursa(job #935494)
#include <fstream>
#include <cstring>
#define NMAX 2000009
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char A[NMAX], B[NMAX], aux[NMAX];
int n, m, pi[NMAX];
int nr, sol[NMAX];
inline void pre() {
int k = 0;
pi[1] = 0;
for(int q = 2; q <= m; ++q) {
while(k > 0 && B[k + 1] != B[q])
k = pi[k];
if(B[k + 1] == B[q]) ++ k;
pi[q] = k;
}
}
int main() {
f.getline(A, NMAX);
f.getline(B, NMAX);
m = strlen(B), n = strlen(A);
if(n < m) {
strcpy(aux, A);
strcpy(A, B);
strcpy(B, aux);
int x = n;
n = m;
m = x;
}
for(int i = n; i >= 1; -- i) A[i] = A[i - 1];
for(int i = m; i >= 1; -- i) B[i] = B[i - 1];
pre();
int q = 0;
for(int i = 1; i <= n; ++i) {
while(q > 0 && B[q + 1] != A[i])
q = pi[q];
if(B[q + 1] == A[i])
++ q;
if(q == m) sol[ ++ sol[0]] = i - m;
}
g << sol[0] << '\n';
for(int i = 1; i <= sol[0]; ++i) g << sol[i] << ' ';
g << '\n';
g.close();
return 0;
}