Pagini recente » Cod sursa (job #2826875) | Cod sursa (job #2465695) | Cod sursa (job #398865) | Cod sursa (job #1849855) | Cod sursa (job #2716494)
#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
const int N = 2000002;
const int P = 1000;
char a[N], b[N];
int pi[N];
bitset <N> c;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (1 + a) >> (1 + b);
in.close();
int lung = 0, m = strlen(1 + a), n = strlen(1 + b);
pi[1] = 0;
for (int i = 2; i <= m; i++)
{
while (lung > 0 && a[i] != a[lung + 1])
{
lung = pi[lung];
}
if (a[i] == a[lung + 1])
{
lung++;
}
pi[i] = lung;
}
lung = 0;
int nr = 0;
for (int i = 1; i <= n; i++)
{
while (lung > 0 && b[i] != a[lung + 1])
{
lung = pi[lung];
}
if (b[i] == a[lung + 1])
{
lung++;
}
if (lung == m)
{
//cout << i - m + 1 << " ";
c[i - m] = 1;
nr++;
}
}
out << nr << "\n";
nr = P;
for (int i = 0; i < n && nr > 0; i++)
{
if (c[i])
{
out << i << " ";
nr--;
}
}
out.close();
return 0;
}