Pagini recente » Cod sursa (job #694593) | Cod sursa (job #2607688) | Cod sursa (job #508913) | Cod sursa (job #1898992) | Cod sursa (job #2716554)
#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 = 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;
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 << "\n";
nr = P;
for(int i = 0; i < n && nr > 0; i++)
{
if(c[i])
{
fout << i << " ";
nr--;
}
}
return 0;
}