Pagini recente » Cod sursa (job #2645754) | Cod sursa (job #534382) | Cod sursa (job #2569379) | Cod sursa (job #25757) | Cod sursa (job #1648132)
# include <fstream>
# include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int L = 2000005;
typedef char sir[L];
sir X, Y;
int Pi[L], D[L];
int N, M, k, i, sol, nr;
int main() {
fin >> (X+1) >> (Y+1);
N = strlen(X+1);
M = strlen(Y+1);
k = 0;
Pi[1] = 0;
for (i=2; i<=N; ++i) {
while (k > 0 && X[i] != X[k+1])
k = Pi[k];
if (X[i] == X[k+1])
++k;
Pi[i] = k;
}
k = 0;
for (i=1; i<=M; ++i) {
while (k > 0 && Y[i] != X[k+1])
k = Pi[k];
if (Y[i] == X[k+1])
++k;
D[i] = k;
if (D[i] == N)
++sol;
}
fout << sol << "\n";
for (i=1; i<=M; ++i) {
if (D[i] == N) {
--sol, ++nr;
fout << i-N << " ";
}
if (sol == 0 || nr == 1000) break;
}
return 0;
}