7-2 破译报文（PTA 字符串实验）-Toy模板网

这篇具有很好参考价值的文章主要介绍了7-2 破译报文（PTA 字符串实验）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

7-2 破译报文

分数 80

作者朱允刚

单位吉林大学

小明接到一个破解报文的任务：该报文是一串文本，破解出的密文应是在报文串中出现次数大于1的所有子串中的最长者。规定报文本身不能称为自己的子串。请编写效率尽可能高的程序帮小明完成这个棘手的任务。

输入格式:

输入为一个字符串，表示报文，包含不超过10000个字母。

输出格式:

输出为一个整数，表示破解出的密文串的长度。

输入样例1:
xabceabcf
输出样例1:
3

具体算法如下：

首先定义一个哈希函数Hash，用于计算字符串的哈希值。哈希值的计算采用了前缀哈希的方式，使用了一个预先设定的质数k和一个模数mod。对于字符串中的每个位置，计算其前缀和的哈希值。

字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到
如 X1X2X3⋯Xn−1Xn 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。相当于将字符串看做一个 P 进制的数字，每个位上的数字值为 ascil码的值。其中  代表  的  次方

   $7-2 破译报文（PTA 字符串实验）,哈希算法,散列表,算法$
s为前缀和数组，str为字符串数组
前缀和公式   $7-2 破译报文（PTA 字符串实验）,哈希算法,散列表,算法$
区间和公式 $7-2 破译报文（PTA 字符串实验）,哈希算法,散列表,算法$
定义一个辅助函数check，用于检查长度为x的子串是否在报文串中出现了多次。该函数使用一个哈希表st来记录已经出现过的子串的哈希值。遍历报文串的所有长度为x的子串，计算其哈希值并判断是否在哈希表中已经存在。如果存在，则说明该子串出现了多次，返回true；否则，将该子串的哈希值添加到哈希表中，并继续遍历下一个子串。最后，如果没有找到重复出现的子串，则返回false。使用前缀和，我们可将查询一个子串的哈希值的时间缩减为。
主函数solve中，首先读入报文串并计算其长度。然后，使用前缀哈希的方式计算字符串的哈希值，并保存在数组s中。同时，计算每个位置的权值p。接下来，使用二分查找的方式找到报文串中出现次数大于1的所有子串中的最长者。初始时，将左边界l设为0，右边界r设为报文串的长度。我们不难看出，答案是具有单调性质的。如果长度为的子串能被找出两次以上，那么长度为的子串也能被找出两次以上。

时间复杂度，空间复杂度文章来源地址https://www.toymoban.com/news/detail-715485.html

#define int long long
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(a, b, c) for (a = b; a <= c; a++)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N = 10010, mod = 1e9 + 7;

int k = 100007;
char str[N];
int s[N],p[N];
int n;
unordered_map <int,bool> st;

int Hash(int l,int r){
    int t = (s[r] - (s[l-1] * p[r-l+1] % mod) + mod) % mod;
    return t;
}

bool check(int x){
    int i;
    st.clear();
    
    rep(i,1,n-x+1){
        int t = Hash(i,i+x-1);
        // cout << ' ' << i << ' ' << i+x-1 <<" HASH is " << t << endl;

        if (st[t]) return 1;
        st[t] = 1;
    }
    return 0;
}

void solve(){
    cin >> str+1;
    n = strlen(str+1);

    int i;
    
    p[0] = 1;
    rep(i,1,n){
        s[i] = (s[i-1] * k + str[i]) % mod;
        p[i] = p[i-1] * k % mod;
    }   

    int l = 0,r = n;

    while (l + 1 != r){
        int mid = l + r >> 1;
        if (check(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }

    cout << l << endl;
}

到了这里，关于7-2 破译报文（PTA 字符串实验）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！