Wikioi - 1040. Counting.

1040.c

/* Wikioi - Problem 1040 count the number of words; . by Abreto. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHARS	(201)
#define	MAX_WORDS	(7)

int k = 0, s = 0;
char str[MAX_CHARS] = {0};
int nstrchrs = 0;
char dic[MAX_WORDS][22] = {{0}};
int nwrdchrs[MAX_WORDS] = {0};
int a[MAX_CHARS] = {0}, b[MAX_CHARS] = {0};
int nwrdsinstr = 0;

int
wrd_compar(const void * s1, const void * s2)
{
	int i = 0;
	char *a = (char *)s1;
	char *b = (char *)s2;
	
	if( strlen(a) != strlen(b) )
		return (strlen(a)-strlen(b));
	
	for(i = 0;i < strlen(a);++i)
		if( a[i] != b[i] )
			return (a[i] - b[i]);
	
	return 0;
}

int count_v[201][201] = {0};
int
count(int i, int j)
{
	int *ans = &(count_v[i][j]);
	int it = 0;
	
	if( *ans > 0 )
		return (*ans);
	
	*ans = 0;
	for(it = 0;it < nwrdsinstr;++it)
		if( a[it] >= i && b[it] <= j )
			++ (*ans);
		else if ( a[it] > j )
			break;
	
	return (*ans);
}

int dp_v[201][41] = {{0}};
int
dp(int i, int k)
{
	int it = 0, jt = 0;
	int *ans = &(dp_v[i][k]);
	int max = 0;
	int tmd = 0;
	
	if( *ans > -1 )
		return (*ans);
	
	if( 1 == k )
		return (*ans = count(0,i));
	
	for(it = i-1;it >= k-2;--it)
	{
		tmd = dp(it, k-1) + count(it+1, i);
		if( max < tmd )
			max = tmd;
	}
	
	return (*ans = max);
}

int
main(void)
{
	int T = 0;
	
	scanf("%d\n", &T);
	while(T--)
	{
		int i = 0, i2 = 0, i3 = 0;
		char line[22] = "";
		int p = 0;
		
		scanf("%d %d", &p, &k);
		for(i = 0;i < p;++i)
		{
			scanf("%s\n", line);
			strcat(str, line);
		}
		scanf("%d", &s);
		for(i = 0;i < s;++i)
			scanf("%s", dic[i]);
		
		qsort(dic, s, sizeof(dic[0]), wrd_compar);
		for(i = 0;i < s;++i)
			nwrdchrs[i] = strlen(dic[i]);
		
		nstrchrs = strlen(str);
		nwrdsinstr = 0;
		for(i = 0;i < nstrchrs;++i)
		{
			for(i2 = 0;i2 < s;++i2)
			{
				for(i3 = 0;i3 < nwrdchrs[i2];++i3)
					if( i+i3 > nstrchrs )
						goto NEXT_POS_;
					else if( str[i+i3] != dic[i2][i3] )
						goto NEXT_WRD_;
				a[nwrdsinstr] = i;
				b[nwrdsinstr++] = i+i3-1;
				break;
NEXT_WRD_:		;
			}
NEXT_POS_:	;
		}
		
		memset(count_v, -1, sizeof(count_v));
		memset(dp_v, -1, sizeof(dp_v));
		
		printf("%d\n", dp(nstrchrs-1, k));
	}
	
	return 0;
}