Pagini recente » Monitorul de evaluare | Cod sursa (job #1794874) | Cod sursa (job #659829) | Istoria paginii runda/ultradp/clasament | Cod sursa (job #547216)
Cod sursa(job #547216)
#include <fstream>
#include <string>
#include <stdio.h>
#include <string.h>
#define N 2000001
#define minim(a, b) ( (a < b) ? a : b)
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
//char a[N], b[N];
string a,b;
int pi[N], pos[1002], n, m, nr;
void prefix()
{
int i, q=0;
for(i=1, pi[0] = 0; i<m; i++)
{
while(q && a[q] != a[i])
q = pi[q-1];
if(a[i] == a[q])
q++;
pi[i] = q;
}
}
int main()
{
int i, q=0, nr=0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
//gets(a);
//gets(b);
//m = strlen(a);
//n = strlen(b);
in >> a >> b;
m = a.size();
n = b.size();
prefix();
//potrivire;
for(i=0; i<n; i++)
{
while(q && a[q] != b[i])
q = pi[q-1];
if(a[q] == b[i])
q++;
if(q == m)
{
q = pi[m-1];
++nr;
if(nr <= 1000)
pos[nr] = i - m + 1;
}
}
printf("%d\n", nr);
for(i=1; i <= minim(nr, 1000); i++)
printf("%d ", pos[i]);
printf("\n");
return 0;
}