USACO Section2.3 Longest Prefix 解题报告 【icedream61】

　　　　prefix解题报告
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　给你许多子串P和一个长字符串S，请问S的前缀中能用这些子串（可以重复使用子串）组合的最长的一个长度是多少？
【数据范围】
　　P的长度在1～10之内，子串个数在1～200之内
　　S的长度在1～200,000之内
【输入格式】
　　首先给出用空白分割的各个子串P，以独处一行的'.'字符作为结束符
　　然后给出S，分多行给出，每行不超过76个字符。注意，分行符不属于S。
【输入样例】
　　A AB BA CA BBC
　　.
　　ABABACABAABC
【输出样例】
　　11
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　简单的DP。
　　输入输出不多说，bool型数组d，定义如下：d[i]==ture表示S长度为i的前缀可以被P表示出来。
　　如此一来，递推下去即可，从d[i]可以更新d[i+P[j].size()]，直至更新到底。
　　假设有K个子串，S串长度为N，则总时间复杂度为O(NK)。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】

　　有一个很严重的问题，我的代码最后一个点评测时运行时间是0.99s~1.04s之间波动，因此可能超时、可能AC……这说明我的算法应当改进，或者进行常数优化，在此特别提醒读者！
　　另外，提交过程中，有几个细节问题，导致没有一次AC。这里不加赘述，因为这些错误并无借鉴意义，仅仅是因为我这道题是写了一半，放了一周，再继续写完的。。。所以错误百出。

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 /*

 ID: icedrea1

 PROB: prefix

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 int K;

 string P[],S;

 bool d[];

 int main()

 {

     ifstream in("prefix.in");

     ofstream out("prefix.out");

     string str;

     for(in>>str;str!=".";in>>str) P[++K]=str;

     //cout<<"K="<<K<<endl;

     //for(int i=1;i<=K;++i) cout<<"P["<<i<<"]="<<P[i]<<endl;

     while(in>>str) S+=str;

     S="."+S;

     //cout<<"12345678901234567890123456789012345678901234567890123456789012345678901234567890";

     //cout<<"S.size="<<S.size()<<endl;

     //cout<<S<<endl;

     d[]=true;

     for(int i=;i!=S.size();++i)

         if(d[i])

         {

             //cout<<"d["<<i<<"]=true"<<endl;

             for(int j=;j<=K;++j)

                 if(S.find(P[j],i+)==i+) d[i+P[j].size()]=true;

         }

     for(int i=S.size();i>=;--i)

         if(d[i]) { out<<i<<endl; break; }

     in.close();

     out.close();

     return ;

 }