Pagini recente » Cod sursa (job #2286933) | Cod sursa (job #1283787) | Cod sursa (job #987695) | Cod sursa (job #2535140) | Cod sursa (job #2191696)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
const int NMAX=2000005;
int n, m, nr, prefix[NMAX], sol[1024];
char a[NMAX], b[NMAX];
int minim(int a, int b)
{
if(a > b)
return b;
return a;
}
void make_prefix()
{
int k=0;
for(int i = 2;i <= m; i++)
{
while( k && a[k + 1] != a[i])
k = prefix[k];
if(a[k + 1] == a[i])
k++;
prefix[i] = k;
}
}
int main()
{
int k = 0;
f.getline(a + 1, NMAX);
f.getline(b + 1, NMAX);
m = strlen(a + 1);
n = strlen(b + 1);
make_prefix();
for(int i = 1; i <= n; i++)
{
while(k && a[k + 1] != b[i])
k = prefix[k];
if(a[k + 1] == b[i])
k++;
if(k == m)
{
k = prefix[m];
nr++;
if(nr <= 1000)
sol[nr] = i - m;
}
}
g << nr << '\n';
for(int i = 1; i <= minim(nr, 1000); i++)
g << sol[i] << ' ';
}