Pagini recente » Monitorul de evaluare | Istoria paginii runda/oni_mixtv12 | Cod sursa (job #1840267) | Cod sursa (job #763650) | Cod sursa (job #2716544)
#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N = 2000002;
const int P = 1000;
char a[N], b[N];
int pi[N];
bitset <N> c;
int main()
{
fin >> (1 + a) >> (1 + b);
int lung = 0, m = strlen(1 + a);
pi[1] = 0;
for(int i = 1; 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;
int n = strlen(1 + b);
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)
{
c[i - m] = 1;
nr++;
}
}
fout << nr;
nr = P;
for(int i = 0; i < n && nr > 0; i++)
{
if(c[i])
{
fout << i << " ";
nr--;
}
}
return 0;
}