第一周 8.30-9.5

8.30

用dp[i]表示以第i个字符结尾的与前缀相同的串数。

转移：dp[i]=dp[Next[i]]+1。

答案即为所有dp求和。

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 int m,Next[200100],dp[200100];
 5 char b[200100];
 6 
 7 void getNext(void)
 8 {        
 9     Next[0]=Next[1]=0;
10     for(int i=1;i<m;i++)
11     {
12         int j=Next[i];
13         while(j&&b[i]!=b[j]) j=Next[j];
14         Next[i+1]=b[i]==b[j]?j+1:0;    
15     }
16     return;
17 }
18 
19 int main(void)
20 {
21     int T; cin>>T;
22     while(T--)
23     {
24         scanf("%d%s",&m,b);
25         getNext();
26         int ans=0;
27         for(int i=1;i<=m;i++)
28         {
29             dp[i]=dp[Next[i]]+1;
30             ans=(ans+dp[i])%10007;
31         }
32         printf("%d
",ans);
33     }
34     return 0;
35 }

Aguin

HDU 4300 Clairewd’s message

题意：给一个加密用字母映射。和一个串。串=密文+部分明文（部分明文长度可以为0）。还原出最短的完整密文+明文。

考虑到密文的长度比如大于整个串的一半。可以取串的前半部分（全是密文）作为一个模式串。

再把原串加密。即由密文+部分明文→二次加密文+部分密文。作为主串。

KMP预处理后。从主串的后半部分开始匹配。容易发现匹配到的最后一次的重叠部分就是原串的密文部分。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 char S[26],R[26];
 6 char str[100100],a[100100],b[50100];
 7 int m,n,Next[50100];
 8 
 9 void getNext(void)
10 {        
11     Next[0]=Next[1]=0;
12     for(int i=1;i<m;i++)
13     {
14         int j=Next[i];
15         while(j&&b[i]!=b[j]) j=Next[j];
16         Next[i+1]=b[i]==b[j]?j+1:0;    
17     }
18     return;
19 }
20 
21 int main(void)
22 {
23     int T; cin>>T;
24     while(T--)
25     {
26         scanf("%s%s",S,str);
27         for(int i=0;i<26;i++) R[S[i]-'a']=i+'a';
28         strcpy(a,str);
29         n=strlen(a),m=(n+1)/2;
30         memcpy(b,a,sizeof(char)*m);
31         b[m]=0;
32         for(int i=0;i<n;i++) a[i]=S[a[i]-'a'];
33         getNext();
34         int j=0,pos;
35         for(int i=m;i<n;i++)
36         {
37             while(j&&b[j]!=a[i]) j=Next[j];
38             if(b[j]==a[i]) j++;
39         }
40         for(int i=0;i<n-j;i++) putchar(str[i]);
41         for(int i=0;i<n-j;i++) putchar(R[str[i]-'a']);
42         puts("");
43     }
44     return 0;
45 }

Aguin

还找到一个exkmp的做法。没用过exkmp试下。

原串作为主串。再把原串反译一遍作为模式串。

求完extend之后。从中间往后找第一个满足ex[i]=n-1的地方就是原串密文的终点。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 char S[26],R[26],a[100100],b[100100];
 7 int Next[100100],ex[100100];
 8 int n,m;
 9 
10 void getNext(void)
11 {
12     int P=1,j; Next[0]=m;
13     for(int i=Next[1]=0;i<m-1&&b[i]==b[i+1];) Next[1]=++i;
14     for(int i=2;i<m;i++)
15     {
16         if(Next[i-P]+i<Next[P]+P) Next[i]=Next[i-P];
17         else
18         {
19             j=max(Next[P]+P-i,0);
20             while(i+j<m&&b[j]==b[j+i]) j++;
21             Next[i]=j; P=i;
22         }
23     }
24     return;    
25 }
26 
27 void exKMP(void)
28 {
29     getNext();
30     int j,P=0;
31     for(int i=ex[0]=0;i<m&&a[i]==b[i];) ex[0]=++i;
32     for(int i=1;i<n;i++)
33     {
34         if(Next[i-P]+i<ex[P]+P) ex[i]=Next[i-P];
35         else
36         {
37             j=max(ex[P]+P-i,0);
38             while(i+j<n&&j<m&&a[j+i]==b[j]) j++;
39             ex[i]=j; P=i;
40         }
41     }
42     return;
43 }
44 
45 int main(void)
46 {
47     int T; cin>>T;
48     while(T--)
49     {
50         scanf("%s%s",S,a);
51         for(int i=0;i<26;i++) R[S[i]-'a']=i+'a';
52         n=m=strlen(a);
53         strcpy(b,a);
54         for(int i=0;i<n;i++) b[i]=R[b[i]-'a'];
55         exKMP();
56         int pos=n;
57         for(int i=(n+1)/2;i<n;i++)
58             if(ex[i]==n-i) {pos=i;break;}
59         for(int i=0;i<pos;i++) putchar(a[i]);
60         for(int i=0;i<pos;i++) putchar(R[a[i]-'a']);
61         puts("");
62     }
63     return 0;
64 }

Aguin

HDU 1238 Substrings

因为n很小。直接暴力搞。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 char str[101][101];
 7 
 8 int main(void)
 9 {
10     int T; cin>>T;
11     while(T--)
12     {
13         int n,Maxl=100,ok; scanf("%d",&n);
14         for(int i=1;i<=n;i++)
15         {
16             scanf("%s",str[i]+1);
17             int tem=strlen(str[i]+1);
18             Maxl=min(Maxl,tem);
19         }
20         int len=strlen(str[1]+1);
21         for(int l=Maxl;l>0;l--)
22         {
23             for(int s=1;s+l-1<=len;s++)
24             {
25                 char s1[101],s2[101];
26                 for(int i=0;i<l;i++) s1[i]=s2[l-i-1]=str[1][s+i];
27                 s1[l]=s2[l]=0;
28                 ok=1;
29                 for(int i=2;i<=n;i++)
30                     if(!strstr(str[i]+1,s1)&&!strstr(str[i]+1,s2))
31                         {ok=0;break;}
32                 if(ok) break;
33             }
34             if(ok) {printf("%d
",l);break;}
35         }
36         if(!ok) puts("0");
37     }
38     return 0;
39 }

Aguin

HDU 2328 Corporate Identity

暴力水果？

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 char str[4001][300];
 7 
 8 int main(void)
 9 {
10     int n;
11     while(~scanf("%d",&n)&&n)
12     {
13         char ans[300]={0};
14         int M=300,pos,flag;
15         for(int i=1;i<=n;i++)
16         {
17             scanf("%s",str[i]+1);
18             int len=strlen(str[i]+1);
19             if(len<M){M=len;pos=i;}
20         }
21         for(int l=M;l>0;l--)
22         {
23             flag=0;
24             for(int s=1;s+l-1<=M;s++)
25             {
26                 char s1[300];
27                 for(int i=0;i<l;i++) s1[i]=str[pos][s+i];
28                 s1[l]=0;
29                 int ok=1;
30                 for(int i=1;i<=n;i++)
31                 {
32                     if(i==pos) continue;
33                     if(!strstr(str[i]+1,s1))
34                         {ok=0;break;}
35                 }
36                 if(ok)
37                 {
38                     if(!flag) strcpy(ans,s1);
39                     else if(strcmp(s1,ans)<0) strcpy(ans,s1);
40                     flag=1;
41                 }
42             }
43             if(flag) {printf("%s
",ans);break;}
44         }
45         if(!flag) puts("IDENTITY LOST");
46     }
47     return 0;
48 }

Aguin

8.31

HDU 3374 String Problem

这个问题可以分解成两个问题。

1.求循环节。这个用前面的Next性质即可。

2.求最小（大）表达法。就是从某个字符开始取使得字典序最小(大)。

学习了一个O(n)的算法。Link。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 int m,Next[1000100];
 6 char b[1000100];
 7 
 8 void getNext(void)
 9 {        
10     Next[0]=Next[1]=0;
11     for(int i=1;i<m;i++)
12     {
13         int j=Next[i];
14         while(j&&b[i]!=b[j]) j=Next[j];
15         Next[i+1]=b[i]==b[j]?j+1:0;    
16     }
17     return;
18 }
19 
20 int get(int op)
21 {
22     int i=0,j=1,k=0;
23     while(i<m&&j<m&&k<m)
24     {
25         int t=b[(i+k)%m]-b[(j+k)%m];
26         if(!t) k++;
27         else
28         {
29             if(op^(t>0)) i=max(i+k+1,j+1);
30             else j=max(j+k+1,i+1);
31             k=0;
32         }
33     }
34     return min(i,j);
35 }
36 
37 int main(void)
38 {
39     while(~scanf("%s",b))
40     {
41         m=strlen(b);
42         getNext();
43         int num=m%(m-Next[m])==0?m/(m-Next[m]):1;
44         printf("%d %d %d %d
",get(0)+1,num,get(1)+1,num);
45     }
46     return 0;
47 }

Aguin

9.1-9.4

什么都没干。

9.5

HDU 2609 How many

最小表示法。直接丢set里去重了。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <string>
 4 # include <cstring>
 5 # include <algorithm>
 6 # include <set>
 7 using namespace std;
 8 string s;
 9 int m;
10 
11 int getMin(void)
12 {
13     int i=0,j=1,k=0;
14     while(i<m&&j<m&&k<m)
15     {
16         int t=s[(i+k)%m]-s[(j+k)%m];
17         if(!t) k++;
18         else
19         {
20             if(t>0) i=max(i+k+1,j+1);
21             else j=max(j+k+1,i+1);
22             k=0;
23         }
24     }
25     return min(i,j);
26 }
27 
28 int main(void)
29 {
30     int n;
31     while(~scanf("%d",&n))
32     {
33         set <string> S;
34         for(int i=1;i<=n;i++)
35         {
36             cin>>s;
37             m=s.size();
38             int pos=getMin();
39             string s1(s.begin()+pos,s.end());
40             string s2(s.begin(),s.begin()+pos);
41             s1+=s2;
42             S.insert(s1);
43         }
44         printf("%d
",S.size());
45     }
46     return 0;
47 }

Aguin

晚上BC待补。