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;
}