字符串Hash模版——字符串


讲解

  • 教程
    教程传送门

  • 复杂度

      设主串为s,被查询串为t,长度分别为n、m
      预处理主串s的复杂度为O(n)
      预处理被查询串的复杂度为O(m)
      每次查询的复杂度为:O(n-m)

    自然溢出代码(通过 unsigned 无符号数据类型 对数据溢出时自动 取余)

    ⚠️自然溢出必须是无符号的数据类型否则的话一旦某个出现数据溢出,这个数就可能变成负数了

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    #include <string>
    #include <queue>
    #include <map>
    #include <set>
    #include <bitset>
    #include <vector>
    #include <stack>
    /* #include <unordered_map> */
    #include <sstream>
    void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
    void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
    #define ios ios::sync_with_stdio(false)
    #define Pi acos(-1)
    #define pb push_back
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define db double
    #define Pir pair<int, int>
    #define m_p make_pair
    #define INF 0x3f3f3f3f
    #define esp 1e-7
    #define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
    #define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
    #define sc scanf
    #define pr printf
    #define sd(a) scanf("%d", &a)
    #define ss(a) scanf("%s", a)
    using namespace std;

    #define mod (ll)(1e9 + 7)
    const int mxn = 1e6 + 10;
    char s[mxn], t[mxn];
    ll hsh1[mxn];
    ll hsh2[mxn];
    ll pre[mxn];
    ll hp = 131;

    void get_hash(char s[], ll hash[], int n)
    {
    for_(i, 1, n)
    hash[i] = hash[i - 1] * hp + s[i];
    }

    void init()
    {
    pre[0] = 1;
    for_(i, 1, mxn - 1)
    pre[i] = pre[i - 1] * hp;
    }

    int main()
    {
    /* fre(); */
    init();
    int T; sd(T);
    while(T --)
    {
    ss(s + 1);
    ss(t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    get_hash(s, hsh1, n);
    get_hash(t, hsh2, m);

    int sum = 0;
    for_(i, n, m)
    {
    ll h = hsh2[i] - hsh2[i - n] * pre[n];
    if(h == hsh1[n]) sum ++;
    }
    pr("%d\n", sum);
    }

    return 0;
    }


    非自然溢出代码(取mod)

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    #include <string>
    #include <queue>
    #include <map>
    #include <set>
    #include <bitset>
    #include <vector>
    #include <stack>
    /* #include <unordered_map> */
    #include <sstream>
    void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
    void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
    #define ios ios::sync_with_stdio(false)
    #define Pi acos(-1)
    #define pb push_back
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define db double
    #define Pir pair<int, int>
    #define m_p make_pair
    #define INF 0x3f3f3f3f
    #define esp 1e-7
    #define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
    #define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
    #define sc scanf
    #define pr printf
    #define sd(a) scanf("%d", &a)
    #define ss(a) scanf("%s", a)
    using namespace std;

    #define mod (ll)(1e9 + 7)
    const int mxn = 1e6 + 10;
    char s[mxn], t[mxn];
    ll hsh1[mxn];
    ll hsh2[mxn];
    ll pre[mxn];
    ll hp = 131;

    void get_hash(char s[], ll hash[], int n)
    {
    for_(i, 1, n)
    hash[i] = (hash[i - 1] * hp + s[i]) % mod;
    }

    void init()
    {
    pre[0] = 1;
    for_(i, 1, mxn - 1)
    pre[i] = pre[i - 1] * hp % mod;
    }

    int main()
    {
    /* fre(); */
    init();
    int T; sd(T);
    while(T --)
    {
    ss(s + 1);
    ss(t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    get_hash(s, hsh1, n);
    get_hash(t, hsh2, m);

    int sum = 0;
    for_(i, n, m)
    {
    int h = ((hsh2[i] - hsh2[i - n] * pre[n]) % mod + mod) % mod;
    if(h == hsh1[n]) sum ++;
    }
    pr("%d\n", sum);
    }

    return 0;
    }

    例题传送门

    原创:https://www.panoramacn.com
    源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

    专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

    字符串Hash模版——字符串

    免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

    您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
    www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
    未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 字符串Hash模版——字符串
    关注我们小说电影免费看
    关注我们,获取更多的全网素材资源,有趣有料!
    120000+人已关注
    分享到:
    赞(0) 打赏
  • 评论抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    您的打赏就是我分享的动力!

    支付宝扫一扫打赏

    微信扫一扫打赏