HDU - 4300 Clairewd’s message （拓展kmp）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=100010;   //字符串长度最大值
 5 int nt[maxn],ex[maxn]; //ex数组即为extend数组
 6 char a[maxn],b[maxn],c[maxn];
 7 map<char,char> mp;
 8 
 9 //预处理计算next数组
10 void GETNEXT(char *str)
11 {
12     int i=0,j,po,len=strlen(str);
13     nt[0]=len;    //初始化nt[0]
14     while(str[i]==str[i+1]&&i+1<len) i++;    //计算nt[1]
15     nt[1]=i;
16     po=1;       //初始化po的位置
17     for(i=2;i<len;i++){
18         if(nt[i-po]+i<nt[po]+po) nt[i]=nt[i-po];    //第一种情况，可以直接得到nt[i]的值
19         else{    //第二种情况，要继续匹配才能得到nt[i]的值
20             j=nt[po]+po-i;
21             if(j<0) j=0;    //如果i>po+nt[po],则要从头开始匹配
22             while(i+j<len&&str[j]==str[j+i]) j++;   //计算nt[i]
23             nt[i]=j;
24             po=i;   //更新po的位置
25         }
26     }
27 }
28 
29 //计算extend数组
30 void EXKMP(char *s1,char *s2)
31 {
32     int i=0,j,po,len=strlen(s1),l2=strlen(s2);
33     GETNEXT(s2);    //计算子串的next数组
34     while(s1[i]==s2[i]&&i<l2&&i<len) i++;   //计算ex[0]
35     ex[0]=i;
36     po=0;   //初始化po的位置
37     for(i=1;i<len;i++){
38         if(nt[i-po]+i<ex[po]+po) ex[i]=nt[i-po];      //第一种情况，直接可以得到ex[i]的值
39         else{    //第二种情况，要继续匹配才能得到ex[i]的值
40             j=ex[po]+po-i;
41             if(j<0) j=0;     //如果i>ex[po]+po则要从头开始匹配
42             while(i+j<len&&j<l2&&s1[j+i]==s2[j]) j++;   //计算ex[i]
43             ex[i]=j;
44             po=i;   //更新po的位置
45         }
46     }
47 }
48 
49 int main()
50 {
51     int t;
52     cin>>t;
53     while(t--){
54         cin>>a>>b;
55         int len1=strlen(a);
56         int len2=strlen(b);
57         for(int i=0;i<len1;i++)
58             mp[a[i]]='a'+i;
59         for(int i=0;i<len2;i++)
60             c[i]=mp[b[i]];
61         c[len2]=0;
62         EXKMP(b,c);
63         int k;
64         for(k=0;k<len2;k++)
65             if(k+ex[k]>=len2&&k>=ex[k]) break;
66         for(int i=0;i<k;i++) cout<<b[i];
67         for(int i=0;i<k;i++) cout<<mp[b[i]];
68         cout<<endl;
69     }
70     return 0;
71 }