Pagini recente » Cod sursa (job #239217) | Cod sursa (job #1698053) | Cod sursa (job #455553) | Cod sursa (job #1093329) | Cod sursa (job #1344398)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int N = 2e6 + 5;
char a[N], b[N];
int U[N], k = 0, m, n;
vector <int> v;
#define min(x,y) ((x)<(y)?(x):(y))
int main() {
fin >> a + 1 >> b + 1;
m = strlen(a+1);
n = strlen(b+1);
for (int i = 2; i <= m; ++i) {
while (k && a[k + 1] != a[i])
k = U[k];
if (a[k + 1] == a[i])
k++;
U[i] = k;
}
for (int i = 1; i <= n; ++i) {
while (k && a[k+1] != b[i])
k = U[k];
if (a[k + 1] == b[i])
k++;
if (k == m) {
v.push_back (i - k);
k = U[k];
}
}
fout << v.size() << "\n";
for (unsigned i = 0; i < min(v.size(), 1000); ++i)
fout << v[i] << " ";
}