Pagini recente » Cod sursa (job #2074939) | Cod sursa (job #2974568) | Cod sursa (job #2680840) | Cod sursa (job #3208192) | Cod sursa (job #2840643)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2e6 + 1;
int N, M;
char A[NMAX], B[NMAX], S[(NMAX << 1)];
int Z[(NMAX << 1)];
static inline void Read ()
{
f.tie(nullptr);
f >> (A + 1), N = (int)strlen(A + 1);
f >> (B + 1), M = (int)strlen(B + 1);
return;
}
static inline int my_min (int a, int b)
{
return ((a < b) ? a : b);
}
static inline void ZFunction ()
{
int L = 0, R = 0;
Z[1] = N + M + 1;
for(int i = 2; i <= N + M + 1; ++i)
{
if(i <= R)
Z[i] = my_min(R - i + 1, Z[i - L + 1]);
else
Z[i] = 0;
while(i + Z[i] <= N + M + 1 && S[i + Z[i]] == S[Z[i] + 1])
++Z[i];
if(i + Z[i] - 1 >= R)
L = i, R = i + Z[i] - 1;
}
return;
}
static inline void Build ()
{
for(int i = 1; i <= N; ++i)
S[i] = A[i];
S[N + 1] = '#';
for(int i = 1; i <= M; ++i)
S[N + 1 + i] = B[i];
ZFunction();
return;
}
static inline void Write ()
{
vector < int > _temp;
for(int i = N + 2; i <= N + M + 1; ++i)
if(Z[i] == N)
_temp.push_back(i - N - 2);
g << (int)_temp.size() << '\n';
for(int i = 0; i < my_min((int)_temp.size(), 1000); ++i)
{
if(i > 0)
g << ' ';
g << _temp[i];
}
if(!_temp.empty())
g << '\n';
return;
}
int main()
{
Read();
Build();
Write();
return 0;
}