Pagini recente » Cod sursa (job #140456) | Cod sursa (job #2630836) | Cod sursa (job #198371) | Cod sursa (job #1056558) | Cod sursa (job #2729417)
#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 >> a >> b;
in.close();
int m = strlen(a), n = strlen(b);
int lung = 0;
for (int i = 1; i < m; i++)
{
while (lung > 0 && a[i] != a[lung])
{
lung = pred[lung];
}
if (a[i] == a[lung])
{
lung++;
}
pred[i] = lung;
}
/*
for (int i = 0; i < m; i++)
{
out << pred[i] << " ";
}
out << "\n";
*/
lung = 0;
for (int j = 0; j < n; j++)
{
while (lung > 0 && b[j] != a[lung])
{
lung = pred[lung];
}
if (b[j] == a[lung])
{
lung++;
}
if (lung == m)
{
poz.push_back(j - m + 1);
lung--;
}
}
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;
}