Skip to content

Instantly share code, notes, and snippets.

@Abreto
Last active December 26, 2015 14:29
Show Gist options
  • Save Abreto/7165847 to your computer and use it in GitHub Desktop.
Save Abreto/7165847 to your computer and use it in GitHub Desktop.
Wikioi - 1040. Counting.
/* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment