Pagini recente » Cod sursa (job #456668) | Cod sursa (job #2279028) | Cod sursa (job #1323697) | Cod sursa (job #2865502) | Cod sursa (job #2951221)
#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;
}