Pagini recente » Cod sursa (job #725875) | Cod sursa (job #1201231) | Cod sursa (job #2880355) | Cod sursa (job #2950775) | Cod sursa (job #143615)
Cod sursa(job #143615)
#include <cstdio>
#include <cstring>
const int maxn = 2000004;
FILE *in = fopen("strmatch.in","r"), *out = fopen("strmatch.out","w");
int n, m;
char a[maxn], b[maxn];
int pi[maxn];
int *v;
void makepi()
{
for ( int i = 2, k = 0; i <= n; ++i )
{
while ( k && a[k+1] != a[i] )
k = pi[k];
if ( a[k+1] == a[i] )
++k;
pi[i] = k;
}
}
int main()
{
fscanf(in, "%s", a + 1);
fscanf(in, "%s", b + 1);
v = new int[maxn];
n = strlen(a + 1);
m = strlen(b + 1);
makepi();
int cnt = 0;
for ( int k = 0, i = 1; i <= m; ++i )
{
while ( k && a[k+1] != b[i] )
k = pi[k];
if ( a[k+1] == b[i] )
++k;
if ( k == n )
v[++cnt] = i - n;
}
fprintf(out, "%d\n", cnt);
int h = cnt < 1000 ? cnt : 1000;
for ( int i = 1; i <= h; ++i )
fprintf(out, "%d ", v[i]);
return 0;
}