# Poj Solution 3043

```http://poj.org/problem?id=3043

#include <stdio.h>

#define max(a,b) ((a)>(b)?(a):(b))

int clac( char *w, int len, char map[32][32], int n, int m ) {
int s[5][1000], sn[5] = {0};
int ans[5][1000] = { 0 }, i, j, k, ii, l, sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<m; j++ )
for( k=0; k<len; k++ )
if( map[i][j] == w[k] )
s[k][sn[k]++] = (i<<5)|j;

for( i=0; i<sn[0]; i++ )
ans[0][i] = 1;
for( i=0; i<len-1; i++ ) {
ii = i+1;
k = 0;
for( j=0; j<sn[i] && k<sn[ii]; j++ )
if( ans[i][j] ){
while( k<sn[ii] && s[ii][k]<=s[i][j] )
k++;
for( l=k; l<sn[ii]; l++ ) {
if( ( s[ii][l] & 31 ) >= ( s[i][j] & 31 ) )
ans[ii][l] += ans[i][j];
}
}
}

for( i=0; i<sn[len-1]; i++ )
sum += ans[len-1][i];
return sum;
}

int main( ) {
char map[32][32], w[10];
int count[256] = { 0 };
int n, m, i, ans = 0, j;

scanf( "%d%d", &n, &m );
for( i=n-1; i>=0; i-- ) {
scanf( "%s", map[i] );
for( j=0; j<m; j++ )
count[map[i][j]]++;
}

while( scanf( "%s", w ) == 1 ) {
for( i=0; w[i]; i++ )
if( count[ w[i] ] == 0 )
break;
if( w[i] == 0 )
ans += clac( w, i, map, n, m );
}
printf( "%dn", ans );
return 0;
}
```
This entry was posted in poj. Bookmark the permalink.