Pagini recente » Cod sursa (job #201237) | Cod sursa (job #1640663) | Cod sursa (job #3205433) | Cod sursa (job #73985) | Cod sursa (job #2951214)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e6;
const int NMAX = 1000;
char a[N+N+2];
int pref[N+N+1];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (a + 1);
int n = strlen(a + 1);
a[n + 1] = '#';
in >> (a + n + 2);
int m = strlen(a + 1);
int lung = 0;
vector <int> ap;
for (int i = 2; i <= m; i++)
{
while (lung > 0 && a[lung + 1] != a[i])
{
lung = pref[lung];
}
if (a[lung + 1] == a[i])
{
lung++;
}
pref[i] = lung;
if (lung == n)
{
ap.push_back(i - 2 * n - 1);
}
}
out << ap.size() << "\n";
int nr_sol = min(NMAX, (int)ap.size());
for (int i = 0; i < nr_sol; i++)
{
out << ap[i] << " ";
}
in.close();
out.close();
return 0;
}