Pagini recente » Cod sursa (job #779382) | Cod sursa (job #563125) | Cod sursa (job #1024234) | Cod sursa (job #1391299) | Cod sursa (job #1129474)
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 200002;
char a[N], b[N];
int pi[N], poz[N];
int n, m, q, nr;
void read ()
{
FILE *fis = fopen ("strmatch.in", "r");
fgets(a, N, fis);
fgets(b, N, fis);
n = strlen(a) - 1;
m = strlen(b) - 1;
for (int i = n; i >= 1; i -- )
a[i] = a[i-1];
for (int i = m; i >= 1; i -- )
b[i] = b[i-1];
a[0] = b[0] = ' ';
fclose(fis);
}
inline int minim (int a, int b)
{
if ( a < b )
return a;
return b;
}
void prefix()
{
int q = 0;
pi[1] = 0;
for (int i = 2; i <= n; ++i )
{
while ( q && a[q+1] != a[i] )
q = pi[q];
if ( a[q+1] == a[i] )
{
++q;
pi[i] = q;
}
}
}
void solve ()
{
prefix();
q = 0, nr = 0;
for (int i = 1; i <= m; i ++ )
{
while ( q && a[q+1] != b[i] )
q = pi[q];
if ( a[q+1] == b[i] )
++ q;
if ( q == n )
{
++ nr;
poz[nr] = i-n;
}
}
}
void write ()
{
FILE *fis2 = fopen ("strmatch.out", "w");
fprintf(fis2, "%d\n", nr);
nr = minim(nr, 1000);
for (int i = 1; i <= nr; i ++ )
fprintf(fis2, "%d ", poz[i]);
fclose(fis2);
}
int main()
{
read();
solve();
write();
return 0;
}