Pagini recente » Cod sursa (job #2641965) | Cod sursa (job #2520323) | Cod sursa (job #240810) | Cod sursa (job #2871093) | Cod sursa (job #1398773)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream is ("strmatch.in");
ofstream os ("strmatch.out");
const int Lmax = 2000003;
int N, M, D[Lmax], cnt;
char Pattern[Lmax], Text[Lmax];
vector <int> S;
int main()
{
is >> Pattern;
is >> Text;
N = strlen(Pattern);
M = strlen(Text);
for (int i = 1, k = 0; i < N; ++i)
{
while (k > 0 && Pattern[k] != Pattern[i])
k = D[k-1];
if (Pattern[k] == Pattern[i])
++k;
D[i] = k;
}
for (int i = 0, k = 0; i < M; ++i)
{
while (k > 0 && Pattern[k] != Text[i])
k = D[k-1];
if (Pattern[k] == Text[i])
++k;
if (k == N)
{
cnt++;
if (S.size() < 1000)
S.push_back(i-N+1);
}
}
os << cnt << '\n';
for (const int& i : S)
os << i << ' ';
is.close();
os.close();
}