Home > Old Blog Posts > USACO 2.3.1 Longest Prefix

USACO 2.3.1 Longest Prefix


DP。

令f[i]为前i个字符可以用前缀表示的长度,若i-j+1..i的部分匹配于某个前缀,则f[i]=max(f[i-j]+j,f[i])。总方程f[i]=max{f[i-j]+j}。边界值f[0]=0。

其中判断是否匹配可以用二分查找实现。

代码:

/*
ID: dementr1
PROG: prefix
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“prefix.in”);
ofstream fout(“prefix.out”);
string S;
string prefix[200];
int pnum=0,f[200001]={},maxl;
void swap(string *a, string *b)
{
string x=*a;
*a=*b;
*b=x;
}
int partition(string A[],int left, int right)
{
int i=(left+right)/2,j;
swap(&A[i],&A[right]);
i=left-1;
for(j=left;j<right;j++)
{
if(A[j]<A[right])
{
i++;
swap(&A[i],&A[j]);
}
}
i++;
swap(&A[i],&A[right]);
return i;
}
void quicksort(string A[], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
bool search(string a)
{
int start,end,mid;
while(1)
{
start=0;
end=pnum-1;
while(1)
{
mid=(start+end)/2;
if(prefix[mid]<a)
start=mid;
else if(prefix[mid]>a)
end=mid;
else return true;
if(end-start<=1)
{
if(prefix[start]==a||prefix[end]==a) return true;
else return false;
}
}
}
}
string copy(int start, int end)
{
string s;
int i;
for(i=start-1;i<end;i++)
s+=S[i];
return s;
}
void work()
{
int i,j,max=-1;
f[0]=0;
for(i=1;i<=S.length();i++)
{
f[i]=-1;
for(j=1;j<=maxl&&i-j+1>=0;j++)
{
if(f[i-j]==-1) continue;
if(f[i-j]+j>f[i]&&search(copy(i-j+1,i)))
f[i]=f[i-j]+j;
if(f[i]>max) max=f[i];
//system(“pause”);
}
}
if(max==-1) fout<<0<<endl;
else fout<<max<<endl;
}
void init()
{
string s_tmp;
maxl=-1;
while(1)
{
fin>>s_tmp;
if(s_tmp==”.”) break;
prefix[pnum++]=s_tmp;
int len=s_tmp.length();
if(len>maxl) maxl=len;
}
while(!fin.eof())
{
if(s_tmp!=”.”)
S+=s_tmp;
fin>>s_tmp;
}
quicksort(prefix,0,pnum-1);
memset(f,0,sizeof(f));
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

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: