加密博客测试

文章目录[x]
  1. 1:Hash 的思想
  2. 2:代码实现
  3. 3:字符串hash的应用




字符串hash

字符串哈希

Hash 的思想

Hash 的核心思想在于,将输入映射到一个值域较小、可以方便比较的范围。

这里说的“值域较小”在不同的情况下意义是不一样的:

哈希表中:值域需要小到能够接受线性的空间和时间。

而在字符串哈希中,值域需要小到能够快速比较(都可以快速比较)。

同时,为了降低哈希冲突率,值域也不能太小。

我们定义一个把字符串映射到整数的函数,这个就是函数,可以很方便的来帮助我们判断两个字符串是否相等,我们希望哈希函数在值不一样的时候,两个字符串一定不同。

另外,反过来不需要成立,oi-wiki把这种条件称为单侧错误。

里面我们最应该关注的是,时间复杂度和的准确率。

一般我们的函数都是多项式的:

这里面的 需要选取得足够合适才行,以使得 函数的值在分布尽量均匀。

如果互质,在输入随机的情况下,这个 函数在上每个值概率相等,此时单次比较的错误率为 。所以,哈希的模数一般会选用大质数。

代码实现

未优化版:

#include <string>
using namespace std;
const int M = 1e9 + 7;
const int B = 233;
typedef long long ll;
int gethash(const string &s) {
  int ans = 0, siz = s.size();
  for (int i = 0; i < siz; ++i) {
    ans = (ll)(ans * B + s[i]) % M;
  }
  return ans;
}
bool cmp(const string &s, const string &t) { return hash(s) == hash(t); }
hash 的分析与改进

错误率:若进行次比较,每次错误率为 ,那么总错误率是 。在随机数据下,若 , ,错误率约为 ,并不足够小,不能忽略。

所以,进行字符串哈希时,经常会对两个大质数分别取模,这样的话哈希函数的值域就能扩大到两者之积,错误率就非常小了。

关于多次询问子串哈希

单次计算一个字符串的哈希值复杂度是 ,其中 为串长,与暴力匹配没有区别,如果需要多次询问一个字符串的子串的哈希值,每次重新计算效率非常低下。

一般采取的方法是对整个字符串先预处理出每个前缀的哈希值,将哈希值看成一个进制的数对取模的结果,这样的话每次就能快速求出子串的哈希了:

表示,那么,其中也可以预处理出来,用乘法逆元或者是在直接比较哈希值的时候等式两边同时乘上的若干次化为整式都可。

这样的话,就可以在的时间复杂度内预处理后达到的计算子串哈希值。

代码实现
#include <string>
using namespace std;
const int B = 233;
typedef long long ll;
ll h[1000005], p[1000005];

void init(string s) {
  p[0] = 1;
  h[0] = 0;
  int len = s.length();
  for (int i = 1; i <= len; ++i) {
    p[i] = p[i - 1] * B;
    h[i] = h[i - 1] * B + s[i - 1];
  }
}

ll gethash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

 

字符串hash的应用

字符串匹配

求出模式串的哈希值后,求出文本串每个长度为模式串长度的子串的哈希值,分别与模式串的哈希值比较即可。

预处理复杂度为,查询为,然后遍历子串比较哈希值,总复杂度kmp的复杂度一样。

HDU1686,求模式串在文本串中出现的次数。

在这里插入图片描述

#include <iostream>
#include <string>

using namespace std;
const int N = 1e6 + 5;
const int B = 233;
typedef long long ll;
ll h[N], p[N];
void init(string s) {
  p[0] = 1;
  h[0] = 0;
  int len = s.length();
  for (int i = 1; i <= len; ++i) {
    p[i] = p[i - 1] * B;
    h[i] = h[i - 1] * B + s[i - 1];
  }
}

ll gethash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string a, b;
    cin >> a >> b;
    init(a);
    int ans = 0, lena = a.length(), lenb = b.length();
    ll hasha = gethash(1, lena);
    init(b);
    for (int i = lenb - lena + 1; i; --i) {
      if (hasha == gethash(i, i + lena - 1)) {
        ans++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}


在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e6 + 10;

int n, m;
int ne[N];
char s[M], p[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> p + 1 >> s + 1;
    int ans = 0, n = strlen(p + 1), m = strlen(s + 1);
    for (int i = 2, j = 0; i <= n; i++) {
      while (j && p[i] != p[j + 1]) {
        j = ne[j];
      }
      if (p[i] == p[j + 1]) {
        j++;
      }
      ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i++) {
      while (j && s[i] != p[j + 1]) {
        j = ne[j];
      }
      if (s[i] == p[j + 1]) {
        j++;
      }
      if (j == n) {
        {
          ans++;
          j = ne[j];
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

 

最长回文子串

首先需要分别预处理正着和倒着的哈希值,然后,二分答案,判断是否可行时枚举回文中心(对称轴),哈希判断两侧是否相等。
POJ3974,求最长回文子串的长度。

时间复杂度为:
在这里插入图片描述

#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6 + 5;
const int bas = 13331;
typedef long long ll;
int hashl[N << 1], hashr[N << 1], p[N << 1];
char s[N << 1];
ll gethash(int hash[], int l, int r) {
  return hash[r] - hash[l - 1] * p[r - l + 1];
}
int main() {
  int t = 1;
  p[0] = 1;
  for (int i = 1; i < 2 * N; i++) {
    p[i] = p[i - 1] * bas;
  }
  while (~scanf("%s", s + 1)) {
    if (strcmp(s + 1, "END") == 0) {
      break;
    }
    int n = strlen(s + 1);
    for (int i = n * 2; i > 0; i -= 2) {
      s[i] = s[i / 2];
      s[i - 1] = 'z' + 1;
    }
    n *= 2;
    for (int i = 1, j = n; i <= n; i++, j--) {
      hashl[i] = hashl[i - 1] * bas + s[i] - 'a' + 1;
      hashr[i] = hashr[i - 1] * bas + s[j] - 'a' + 1;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
      int l = 0, r = min(i - 1, n - i);
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (gethash(hashl, i - mid, i - 1) !=
            gethash(hashr, n - (i + mid) + 1, n - (i + 1) + 1)) {
          r = mid - 1;
        } else {
          l = mid;
        }
      }
      if (s[i - l] == 'z' + 1) {
        ans = max(ans, l);
      } else {
        ans = max(ans, l + 1);
      }
    }
    printf("Case %d: %d\n", t++, ans);
  }

  return 0;
}

manacher的时间复杂度:
在这里插入图片描述

#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
char s1[N * 2], s2[N * 2]; // 开双倍数组
int p[N * 2], n; // p数组记录每点的回文长度, n记录数组长度

int manacher() {
  int mx = 0, id, ans = 0;
  for (int i = 1; i < n; ++i) {
    if (mx > i) {
      p[i] = min(p[2 * id - i], mx - i);
    } else {
      p[i] = 1;
    }
    while (s2[i + p[i]] == s2[i - p[i]]) {
      ++p[i];
    }
    if (p[i] + i > mx) {
      mx = p[i] + i, id = i;
    }
    if (p[i] > ans) {
      ans = p[i];
    }
  }
  return ans;
}

void init() { // 使字符长度变为两倍
  s2[0] = s2[1] = '#';
  for (int i = 0; i < n; ++i) {
    s2[(i << 1) + 2] = s1[i], s2[(i << 1) + 3] = '#';
  }
  n = (n << 1) + 2;
  s2[n] = '?';
}

int main() {
  int t = 1;
  while (~scanf("%s", s1)) {
    if (strcmp(s1, "END") == 0) {
      break;
    }
    n = strlen(s1);
    init();
    printf("Case %d: %d\n", t++, manacher() - 1);
  }
  return 0;
}


点赞
  1. Briannix说道:

    blog read this post here go to this website

  2. Undermameecetot说道:

    how does cbd work how to make cannabis oil cbd oil for pets cbd oil uses

  3. BifePyncexciniA说道:

    green roads cbd koi cbd bluebird cbd

  4. BifePyncexciniA说道:

    cbd gummies for sale walmart where to buy cbd oil near me cbd and sleep

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像