Pagini recente » Cod sursa (job #1038010) | Cod sursa (job #2130530) | Cod sursa (job #954675) | Cod sursa (job #2711841) | Cod sursa (job #2951225)
#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;
int n = strlen(a);
a[n] = '#';
in >> (a + n + 1);
int m = strlen(a);
int lung = 0;
vector <int> ap;
for (int i = 1; i < m; i++)
{
while (lung > 0 && a[lung] != a[i])
{
lung = pref[lung-1];
}
if (a[lung] == a[i])
{
lung++;
}
pref[i] = lung;
if (lung == n)
{
ap.push_back(i - 2 * n);
}
}
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;
}