这是一个一维的DP算法题。
1 #include <iostream>
2 #include <fstream>
3 #include <string>
4 #include <string.h>
5 using namespace std;
6 //#define MaxMap 200
7 //#define MaxLen 10
8 ofstream fout ("prefix.out");
9 ifstream fin ("prefix.in");
10 //vector<string> vec;
11 //
12 //char prefix[MaxMap+1][MaxLen+];
13 //int nump;
14 string str="";
15 char prim[11][201][11];//一个char类型的三维数组，方便按串的长度索引字典
16 int MAX_len=0;
17 int len_s=0;
18 int re[200001]={0};//一维的结果数组，在此一维数组中找最大（最优）的那个值，因此此题为一维DP算法题
19 int Num_Prim[11]={0};//一个一维int类型数组，来记录各长度的串的个数
20 //long long len[200001];
21 //#define MAX_LEN
22 void getInput();
23 int calLen();
24 //bool cmp(string s1,string s2)
25 //{
26 // int l1=s1.size();
27 // int l2=s2.size();
28 // return (l1>l2?true:false) ;
29 //}
30 int main() {
31
32 getInput();
33 //sort(vec.begin(),vec.end(),cmp);
34
35 fout << calLen()<<endl;
36 return 0;
37 }
38 bool comp(int p,int num_prim,int l )//p代表str中字符的位置，k代表要匹配的字符串的长度,num_prim代表匹配字符串的索引
39 {
40 for(int i=0;i<l;i++)
41 if (str[p-1-i]!=prim[l][num_prim][l-1-i])
42 {
43 return false;
44 }
45 return true;
46 }
47 int calLen()
48 {
49
50 int ans=0;
//以下是三重循环，用来分别计算str中每一个字符所在的prefix长度
51 for (int i=1;i<=len_s;i++)//字符串str从0开始
52 {
53 for (int j=1;j<=MAX_len&&j<=i;j++)//匹配字符串的长度
54 {
55 for (int k=1;k<=Num_Prim[j];k++)//同一长度的字符串挨个匹配
56 {
57 if (comp(i,k,j)&&re[i-j]==i-j)//后一句判断前面的字符是否已全部匹配
58 {
59 re[i]=i;
60 }
61 }
62 }
63 }
64 for (int i=0;i<=len_s;i++)
65 {
66 if (re[i]>ans)
67 {
68 ans=re[i];
69 }
70 }
71 return ans;
72 }
73 void getInput()
74 {
75
76 char s[200];
77 while(fin>>s&&s[0]!='.')
78 {
79
80 int tl=strlen(s);
81 strcpy(prim[tl][++Num_Prim[tl]],s);
82 if (tl>MAX_len)
83 {
84 MAX_len=tl;//字符表中的最大长度字符串
85 }
86 }
87 while(fin>>s)
88 {
89 /*strcat(str,s);*/
90 str+=s;
91 }
92 len_s=str.length();//输入字符的长度
93
94 // while(getline(fin,s))//多行字符串赋给一个字符串
95 //{
96 // str+=s;
97 //}
98 }
今天父亲节，中午吃完饭之后，拔通了家里的电话，接电话的正是爸爸，几句谈笑之后，我直转正题：爸爸，今天是父亲节，祝……未等我把话说完，爸爸几句话想要转开的意思，其实我鼓起勇气准备第一次亲口祝他节日快乐，而他却还不太好意思，毕竟在中国人们还是习惯了含蓄，把话埋在心里，以往我也是这样想，就一直没有在这种节日时往家里打过电话，但我知道，爸爸今天很高兴，像个孩子一般。我也长长舒了口气，心里特别舒畅，因为我没有觉得把爱表达出来会有什么不妥，反而，我与爸爸更能聊得开了，现在，作为女儿的我已经完全不用他们再操什么心了，现在，他们再也不必像以前一样唠唠叨叨什么了，然而，与此同时，他们快要慢慢地在心理上“蜕化”为孩子了，更需要子女与他们的交流，更需要子女对他们的关心了，而一声节日的祝福，于我而言，几句话语而已，而在他们心里，比蜜还甜。而我，何尝不是呢，爸爸妈妈，我爱你们！
今天，也是一位好友的生日，昨晚给他发了祝福的短信，收到了他真心的感谢，心里真的很高兴。作为朋友，我一直坚信我们的友谊很深厚，于是平时过节也就心里表达着祝福和关怀，但很少亲口说出来，但昨晚的短信，内容虽然很平凡，也就表达了一下美好的祝福，但朋友回了几个字，也是很简单的几个字，我却能感觉到他内心的开心，我也很开心，我会一直默默地祝福你的，亲爱的朋友！
今天周末，傍晚，天气凉爽，吃过晚饭，我慵懒地准备回实验室，BF说带我去隔壁学校转转，我们学校是工科院校，人才济济，校风严谨，拥有迷你型的校园，那个学校却不一样，它带有更多的历史人文气息，校园里透露着一种开阔与舒适，美女如云，设施齐全，是一所百年老校。之前一直都没怎么过来玩过，当我发现它们的操场时，我兴奋的心情开始把我平静的心打开，那里的器械是我见过的种类最多的，而且很多器械我以前都没在哪里见过，更重要的是那里还有两把可以荡起来的坐椅，也算是“秋千”的一种，随着“秋千”的此起彼伏，我的心也跟着荡漾开来，先是一阵“恐高”，再后来就是享受了，风吹过长发，前方的足球场上活跃着不少矫健的身影，远方，天空的云正在发生着美妙的变化，淡蓝的天空，在一方晚霞的照映下显得格外漂亮，风慢慢大起来，慢慢地空中的乌去多了些，风搅动着那些云，像有一双看不见的手在偌大的画面上作着泼墨的山水画……一切都汇聚成美的元素，流到心里，滋养了我干涸的心灵。
生活中不是没有美，而是我们常常忘了去发现，去尝试，去放开心体验，研究生的生活是单调了些，身上的压力是越来越大了些，然而这也不妨碍我们去丰富自己的生活和人生，除了现在的专业学习以外，我也可以追求自己的兴趣爱好，我也可以好好去欣赏学校外面的风景，我也可以去外面的世界中发现新的亮点，我可以把那所学校作为我的后花园……心有多宽，生活就会有多宽，生活中的欢乐也会多起来！
所以，心宽了，皱眉报怨的时间就可以节约下来追求自己的兴趣爱好，追求自己想要的生活，只要有了梦想和追求，你的眼睛将不再没有光采，你的面容将不再有了愁容，你将不再消极，而是拥有美丽心情！
现在，让我大声宣布：开博啦！不管多忙，我都会本着一颗认真生活的心，将这里好好打点，希望以后回过头来时，发现，原来生活赐予我的比我想像的还有多！
对生活心存感激！