USACO OPEN08 wordpow Analysis

USACO OPEN08 Problem 'wordpow' Analysis

by Mohamed Mahmoud Abd El-Wahab

Since we can check that if a good string is a subsequence of a name in O(length of the name) by keeping track of the index of the next character being searched for and when we find it just increment that index

			x=0;
			for(y=0;name[i][y];y++)
			{
				if(name[i][y]==good[j][x])
					x++;
				if(!good[j][x]){
					//the good string j is a subsequence of name i
				}
			}

Then a simple brute force solution can be written as

Foreach name i
	Foreach good string j
		If(string j is a subsequence of name i)
			Increment the counter

The following is a sample solution:

/*
 TASK: wordpow
 LANG: C++
 */
#include 
#include 
using namespace std;
char good[100][1000], name[1000][1002];
int n, m;
int main() {
	freopen("wordpow.in", "rt", stdin);
	freopen("wordpow.out", "wt", stdout);
	scanf("%d%d",&n,&m);
	for (int i = 0; i < n; ++i) {
		scanf("%s",name[i]);
		for (int j = 0; name[i][j]; ++j) {
			name[i][j]=tolower(name[i][j]);			
		}
	}
	for (int i = 0; i < m; ++i) {
		scanf("%s",good[i]);
		for (int j = 0; good[i][j]; ++j) {
			good[i][j]=tolower(good[i][j]);			
		}

	}
	int y,x,c;
	for (int i = 0; i < n; ++i) {
		c=0;
		for (int j = 0; j < m; ++j) {
			x=0;
			for(y=0;name[i][y];y++)
			{
				if(name[i][y]==good[j][x])
					x++;
				if(!good[j][x]){
					c++;break;
				}
			}
		}
		printf("%d\n",c);
	}
	return 0;
}