Pagini recente » Cod sursa (job #2505335) | Cod sursa (job #3274754) | Cod sursa (job #1954399) | Cod sursa (job #433357) | Cod sursa (job #856605)
Cod sursa(job #856605)
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#define pb push_back
using namespace std;
int N, M, cnt;
char A[2000011];
char B[2000011];
int Pi[2000011];
int v[1011];
void Citire ()
{
ifstream fin ("strmatch.in");
fin >> (B + 1) >> (A + 1);
N = strlen (A + 1);
M = strlen (B + 1);
fin.close ();
}
void Precalculare ()
{
Pi[1] = 0;
int p = 0;
for (int i = 2; i <= M; i++)
{
for (; B[i] != B[p + 1] && p > 0;) p = Pi[p];
if (B[i] == B[p + 1]) p++;
Pi[i] = p;
}
}
void Business ()
{
int p = 0;
for (int i = 1; i <= N; i++)
{
for (; A[i] != B[p + 1] && p > 0;) p = Pi[p];
if (A[i] == B[p + 1]) p++;
if (p == M)
{
if (cnt < 1000) v[cnt] = i - M;
cnt++;
p = Pi[p];
}
}
}
void Scriere ()
{
ofstream fout ("strmatch.out");
fout << cnt << "\n";
cnt = min (cnt, 1000);
for (int i = 0; i < cnt; i++)
fout << v[i] << " ";
fout.close ();
}
int main ()
{
Citire ();
Precalculare ();
Business ();
Scriere ();
return 0;
}