# Poj Solution 3167

http://poj.org/problem?id=3167

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

int ss[26][25010], sn[27], last[26];
int aa[26][100010], an[27], S, N, K;
int pos[26][100010];
int next[25010];
int sign[130000];
int flag[130000];

void clac_next( int a[], int n ) {

int i=1, j=0;
next[1] = 0;

while( i <= n ) {
if( j == 0 || a[i] == a[j] ) {
i++, j++;
if( a[i] != a[j] ) next[i] = j;
else next[i] = next[j];
}
else
j = next[j];
}
}

void clac( int skey, int akey, int last_skey ) {
int i=1, j = 1, n=an[akey], m=sn[skey], l=last[skey];
int *a = aa[akey], *s = ss[skey], *p = pos[akey];

if( sn[skey] == 0 ) {
for( i=0; i<=n; i++ ) {
if( flag[*p+l] == last_skey && sign[*p+l] < akey ) {
sign[*p+l] = akey;
flag[*p+l] = skey;
}
p++;
}
return;
}

p++;
while( i <= n ) {
if( j == 0 || a[i] == s[j] ) {
if( j == m && flag[*p+l] == last_skey && sign[*p+l] < akey ) {
sign[*p+l] = akey;
flag[*p+l] = skey;
}
i++, j++, p++;
}
else
j = next[j];
}
}

void input( ) {
int i, t;
int h[26] = { 0 }, g[26] = { 0 };

scanf( "%d%d%d", &N, &K, &S );

for( i=1; i<=S; i++ ) {
an[i] = 0;
sn[i] = 0;
}

for( i=1; i<=N; i++ ) {
scanf( "%d", &t );
if( h[t] ) {
aa[t][ ++an[t] ] = i-h[t];
pos[t][ an[t] ] = i;
}
else {
aa[t][0] = i;
pos[t][0] = i;
}
h[t] = i;
}

for( i=1; i<=K; i++ ) {
scanf( "%d", &t );
if( g[t] )
ss[t][ ++sn[t] ] = i-g[t];
else
ss[t][0] = i;
ss[t][sn[t]+1] = -1;
g[t] = i;
}

for( i=1; i<=S; i++ )
last[i] = -g[i]+1;
}

void doit( ) {
int i, j, count = 0, r = 0;

for( i=1; i<=S; i++ ) {
if( sn[i] || ss[i][0] ) {
clac_next( ss[i], sn[i] );
for( j=1; j<=S; j++ )
if( an[j] >= sn[i] && aa[j][0] )
clac( i, j, r );
r = i;
}
}

for( i=1; i<=N-K+1; i++ )
if( flag[i] == r )
count++;

printf( "%dn", count );

for( i=1; i<=N-K+1; i++ )
if( flag[i] == r )
printf( "%dn", i );
}

int main( ) {

input( );

doit( );

return 0;
}

This entry was posted in poj. Bookmark the permalink.