Pagini recente » Cod sursa (job #1466196) | Cod sursa (job #1358900) | Cod sursa (job #3159383) | Cod sursa (job #1735126) | Cod sursa (job #2729402)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2 + 2e6;
const int NMAX = 1e3;
char a[N], b[N];
int pred[N];
vector<int> poz;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (1 + a) >> (1 + b);
in.close();
int m = strlen(1 + a), n = strlen(1 + b);
int lung = 0;
for (int i = 2; i <= m; i++)
{
while (lung > 0 && a[i] != a[lung + 1])
{
lung = pred[lung];
}
if (a[i] == a[lung + 1])
{
lung++;
}
pred[i] = lung;
}
lung = 0;
for (int j = 1; j <= n; j++)
{
while (lung > 0 && b[j] != a[lung + 1])
{
lung = pred[lung];
}
if (b[j] == a[lung + 1])
{
lung++;
}
if (lung == m)
{
poz.push_back(j - m);
}
}
out << poz.size() << "\n";
if (poz.size() > NMAX)
{
poz.erase(poz.begin() + NMAX, poz.end());
}
for (auto p: poz)
{
out << p << " ";
}
out.close();
return 0;
}