UESTC 1705 咸鱼钟大爷 随机化+哈希

1705 咸鱼钟大爷随机化+哈希

Source

2017 UESTC Training for Search Algorithm & String

My Solution

题意：给出一个p和mod，求出一对哈希冲突的字符串（长度可以不同）

随机化+哈希
随机生成字符串，然后哈希，然后判断f[hashval]是否出现过，如果出现过就找到了哈希冲突的字符串。
如果枚举到MAXN还是没有找到就换一个哈希种子重新找，这里由于oj把ctime禁用了，
所以可以每次定义一个变量，然后用这个变量的地址作为哈希种子。
关于可以使用随机化的原因，请搜索“生日攻击”百科，里面有详细证明。
复杂度 O(n)

#include 
#include 
#include 
#include
#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 1e6;

LL p, MOD;
char s[MAXN+8];

inline LL mod(LL x){
    return x - x / MOD * MOD;
}

inline int getASCII(int i)
{
    s[i] = char(rand()%26 + 'a');
    return int(s[i]);
}

map<LL, int> mp;

int main()
{
    #ifdef LOCAL
    freopen("h.txt", "r", stdin);
    //freopen("h.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    scanf("%lld%lld", &p, &MOD);
    bool ans = false;
    int i, ind, cnt = 0;

    while(true){
        if(ans) break;
        mp.clear();
        LL hashv, last;
        cnt+=19;
        cnt = max(cnt, 1);
        srand(int(&hashv) + cnt);
        last = mod(getASCII(0));
        mp[last] = 0;
        for(i = 1; i < MAXN; i++){
            hashv = mod(last*p+getASCII(i));
            //printf("%sn", s);
            if(mp.find(hashv) != mp.end()){
                s[i+1] = '�';
                printf("%sn", s);
                s[mp[hashv]+1] = '�';
                printf("%sn", s);
                ans = true;
                //cout << hashv << " " << hashmap[ind] << endl;
                break;

            }
            last = hashv;
            mp[last] = i;
        }

    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

UESTC 1705 咸鱼钟大爷随机化+哈希

1705 咸鱼钟大爷随机化+哈希

Source

My Solution

相关推荐

Codeforces Round #353 (Div. 2) B. Restoring Painting __ map or set 、思维题

OpenJ_POJ C16D Extracurricular Sports 找规律、大整数类

Codeforces Round #369 (Div. 2) B. Chris and Magic Square 数学、幻方

Summer Training Team Selection (1) Problem D Hidden Password STL,字符串匹配,简单题

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1705 咸鱼钟大爷 随机化+哈希

1705 咸鱼钟大爷 随机化+哈希

Source

My Solution

相关推荐

Codeforces Round #353 (Div. 2) B. Restoring Painting __ map or set 、思维题

OpenJ_POJ C16D Extracurricular Sports 找规律、大整数类

Codeforces Round #369 (Div. 2) B. Chris and Magic Square 数学、幻方

Summer Training Team Selection (1) Problem D Hidden Password STL,字符串匹配,简单题

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1705 咸鱼钟大爷随机化+哈希

1705 咸鱼钟大爷随机化+哈希