3167.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3167  User Id:fzk 
Memory:1992K  Time:418MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <algorithm>

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( "%d\n", count );

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

int main( ) {
	
	input( );
	
	doit( );

	return 0;
}