Pagini recente » Cod sursa (job #1447327) | Cod sursa (job #1362630) | Cod sursa (job #3039154) | Cod sursa (job #1240585) | Cod sursa (job #1781502)
#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<math.h>
#include<unordered_set>
#include<set>
#include<iomanip>
#include<bitset>
using namespace std;
int M, N;
char A[2002002], B[2002002];
int pi[2002002], pos[1010];
void make_prefix(void)
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= M; ++i)
{
while (q && A[q + 1] != A[i])
q = pi[q];
if (A[q + 1] == A[i])
++q;
pi[i] = q;
}
}
int i, q = 0, n = 0;
int main(void)
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> (A+1);
M = strlen(A+1);
f >> (B+1);
N = strlen(B+1);
make_prefix();
for (i = 1; i <= N; ++i)
{
while (q && 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;
}
}
g << n << '\n';
for (i = 1; i <= min(n, 1000); i++)
g << pos[i]<<' ';
g << '\n';
return 0;
}