Pagini recente » Cod sursa (job #2260724) | Cod sursa (job #1186377) | Cod sursa (job #1201881) | Cod sursa (job #1458871) | Cod sursa (job #1947707)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#define NMax 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int M, N, q, n, w;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];
int main()
{
in.get(A, NMax);
in.get();
in.get(B, NMax);
M = strlen(A);
N = strlen(B);
for (int i = M; i >= 1; i--)
A[i] = A[i-1];
A[0] = ' ';
for (int i = N; i >= 1; i--)
B[i] = B[i-1];
B[0] = ' ';
for (int j = 2; pi[1] = 0, j <= M; j++)
{
while (w != 0 && A[w+1] != A[j])
w = pi[w];
if (A[w+1] == A[j])
++w;
pi[j] = w;
}
for (int i = 1; i <= N; i++)
{
while (q != 0 && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
q++;
if (q == M)
{
q = pi[M];
n++;
if (n <= 1000)
pos[n] = i - M;
}
}
out << n << '\n';
for (int i = 1; i <= min(n, 1000); i++)
out << pos[i] << ' ';
return 0;
}