Longest Prefix——usaco心得

这是一个一维的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 }



posted on 2010-03-04 21:24 碧云天 阅读(501) 评论(0)  编辑 收藏 引用 所属分类: c++基础


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

收藏夹

Emgu CV ——c#版的opencv

Help

搜索

最新评论

阅读排行榜

评论排行榜