Pagini recente » Cod sursa (job #1718922) | Cod sursa (job #3131035) | Cod sursa (job #321232) | Cod sursa (job #2399805) | Cod sursa (job #1624135)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int N = 20000001;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[1 + N], b[1 + N];
int pred[N], m, n, r[N], nr;
void construiestePred()
{
int i, k = 0;
for (i = 2; i <= m; i++)
{
while (k != 0 && a[i] != a[1 + k])
k = pred[k];
if (a[i] == a[1 + k])
k++;
pred[i] = k;
}
}
void cautaInB()
{
int i, k = 0;
for (i = 1; i <= n; i++)
{
while (k != 0 && b[i] != a[1 + k])
k = pred[k];
if (b[i] == a[1 + k])
k++;
if (k == m)
r[++nr] = i - m;
}
}
void scrieRez()
{
int i;
out << nr << "\n";
if (nr > 1000)
nr = 1000;
for (i = 1; i <= nr; i++)
out << r[i] << " ";
out.close();
}
int main()
{
in.getline(1 + a, N);
m = strlen(1 + a);
in.getline(1 + b, N);
n = strlen(1 + b);
in.close();
construiestePred();
cautaInB();
scrieRez();
return 0;
}