Pagini recente » Cod sursa (job #477618) | Cod sursa (job #3285454) | Cod sursa (job #2523130) | Cod sursa (job #2671367) | Cod sursa (job #143616)
Cod sursa(job #143616)
#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[1002];
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);
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 )
{
++cnt;
if ( cnt <= 1000 )
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;
}