Pagini recente » Cod sursa (job #665485) | Cod sursa (job #1548251) | Cod sursa (job #900092) | Cod sursa (job #1117042) | Cod sursa (job #1375235)
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
char A[2000002], B[2000002];
int Q[2000002], res;
vector<int> V;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> (A + 1) >> (B + 1);
N = strlen(A + 1);
M = strlen(B + 1);
int qnow = 0;
for (int i = 2; A[i] != 0; ++i)
{
while (qnow != 0 && A[qnow + 1] != A[i])
qnow = Q[qnow];
if (A[qnow + 1] == A[i])
++qnow;
Q[i] = qnow;
}
qnow = 0;
for (int i = 1; B[i] != 0; ++i)
{
while (qnow != 0 && A[qnow + 1] != B[i])
qnow = Q[qnow];
if (A[qnow + 1] == B[i])
++qnow;
if (qnow == N)
{
++res;
if (V.size() < 1000)
V.push_back(i - N);
qnow = Q[qnow];
}
}
fout << res << '\n';
for (int i = 0; i < int(V.size()); ++i)
fout << V[i] << ' ';
fout << '\n';
fin.close();
fout.close();
}