USACO 2.3.1 – The Longest Prefix


#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
	int best = -1, n = -1, v[200001] = { 0 }, sz[202];
	char pre[202][11], s[200002], t[80];
	freopen("prefix.in", "r", stdin), freopen("prefix.out", "w", stdout);

	do {
		scanf("%s", pre[++n]);
		sz[n] = strlen(pre[n]);
	} while (pre[n][0] != '.');
	while (scanf("%s", t) != -1)
		strncat(s, t, sizeof t);
	
	stack<int> stk; stk.push(0); v[0] = 1;
	
	while (stk.size()) {
		int from = stk.top(); stk.pop();
		best = max(best, from);
		for (int i = 0; i < n; i++) 
			if (!strncmp(s + from, pre[i], sz[i]) && !(v[from + sz[i]]++))
				stk.push(from + sz[i]);
	}
	printf("%d\n", best);
	return 0;
}

Advertisements

One thought on “USACO 2.3.1 – The Longest Prefix

  1. thetaleofsnow says:

    smart!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: