KMP HDOJ 4300 Clairewd's message-白红宇

KMP HDOJ 4300 Clairewd's message

阅读量：6208 次

发布时间：2019-06-21

本文共 1541 字，大约阅读时间需要 5 分钟。

题意：完全不懂，最后还是看题解才理解了。第一行字符串是密文变成明文的规则，比如第二个样例：“qwertyuiopasdfghjklzxcvbnm”，‘q'对应的明文为’a'，'w'对应'b'....... 第二行是密文+明文的形式，明文有密文转换来，但不完整，求原来最小的可能文本。

分析：将密文+明文都当做密文转成明文，那么转换后的字符串前缀密文的部分解密，和原来的字符串的后缀明文匹配，从原来字符串的后半部分和转换之后的字符串的开头开始匹配，得到的是明文(密文)的长度。

收获：题目读不懂多读几遍，再不行yy题意，想想会涉及什么算法

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-24 19:42:24* File Name     :A.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;char ch[30], m[30], s[N], rs[N];int fail[N];void get_fail(char *P, int lenp) { int i = 0, j = -1; fail[0] = -1; while (i < lenp) { if (j == -1 || P[j] == P[i]) { i++; j++; fail[i] = j; } else j = fail[j]; }}int KMP(char *T, char *P) { int lent = strlen (T), lenp = strlen (P); get_fail (P, lenp); int i = 0, j = 0; while (i < lent) { while (j != -1 && T[i] != P[j]) j = fail[j]; i++; j++; } return j;}int main(void) { int T; scanf ("%d", &T); while (T--) { scanf ("%s%s", &ch, &s); for (int i=0; i<26; ++i) { m[ch[i]-'a'] = 'a' + i; } int len = strlen (s); for (int i=0; i

转载于:https://www.cnblogs.com/Running-Time/p/4755900.html

你可能感兴趣的文章