prefix.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: prefix
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
string things[300];int tl[300];
int thingsnum=1;
bool f[200001]={0};int minSlength=999,maxSlength=0;
char fuck[200001];
char tfuck[100];
int answer=0;
string num="";
#define MAX(A,B) (A>B?A:B)
#define MIN(A,B) (A<B?A:B)
int main()
{
	char t;
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	while(true)
	{
		scanf("%c",&t);
		if(t==' '||t=='\n')
		{
			tl[thingsnum]=things[thingsnum].length();
			minSlength = MIN(minSlength,tl[thingsnum]);
			maxSlength = MAX(maxSlength,tl[thingsnum]);
			thingsnum++;
		}
		else if(t<='Z'&&t>='A')
			things[thingsnum]+=t;
		else if(t=='.')
		{thingsnum--;gets(tfuck);break;}
		
	}
	while(gets(tfuck)!=NULL)
		for(int a=1;a<=strlen(tfuck);a++)
			num+=tfuck[a-1];
	int l = num.length();bool tcount;
	f[0]=true;
	for(int a=1;a<=l;a++)
	{
		tcount=false;
		for(int b=a-1;b>=MAX(a-maxSlength,0);b--)
			tcount=tcount||f[b];
		if(!tcount)
			break;
		for(int c=1;c<=thingsnum;c++)
			if(((a-tl[c])>=0)&&f[a-tl[c]])
			{
				tcount=true;
				if(num.substr(a-tl[c],tl[c])==things[c])
				{
					f[a]=true;
					answer=a;
					break;
				}
			}
	}
	printf("%d\n",answer);
	return 0;
}