Pagini recente » Cod sursa (job #1644450) | Cod sursa (job #1816650) | Cod sursa (job #1155225) | Cod sursa (job #820352) | Cod sursa (job #1303223)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int N, M, k, nr, V[2000010], Sol[2000010];
string A, B;
void Prefix()
{
int k = 0;
for (int i = 1; i < N; i++)
{
if (k && A[k] != A[i]) k = V[k-1];
if (A[k] == A[i]) k++;
V[i] = k;
}
}
int main()
{
fin >> A >> B;
N = A.size(); M = B.size();
Prefix();
for (int i = 0; i < M; i++)
{
while (k && A[k] != B[i]) k = V[k-1];
if (A[k] == B[i]) k++;
if (k == N)
{
k = V[k-1];
if (++nr <= 1000) Sol[nr] = i - N + 1;
}
}
fout << nr << '\n';
for (int i = 1; i <= 1000 && i <= nr; i++) fout << Sol[i] << ' ';
fout.close();
return 0;
}