hash hacker

一.单哈希

https://oi-wiki.org/string/hash/

二.双哈希

首先构造两个字符串 \(A,B\) 满足其在 \((b_1,p_1)\) 下哈希值相同，这样由 \(A,B\) 组成的字符串在 \((b_1,p_1)\) 下哈希值相同

再使用一次卡单哈希的构造方法即可。

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define MAXN 60000

int b1 , p1 , b2 , p2;
struct node {
    char s[ 32 ]; int hs;
}a[ MAXN + 5 ] , b[ MAXN + 5 ];
int cmp( const void *a , const void *b ) {
    struct node *aa = a;
    struct node *bb = b;
    return ( aa->hs > bb->hs ) ? 1 : -1;
}
char s[ 2 ][ 7 ]; int hs[ 2 ];

int main( ) {
    srand( 2024 );

    scanf("%d %d",&b1,&p1);
    scanf("%d %d",&b2,&p2);

    for( int i = 1 ; i <= MAXN ; i ++ ) {
        for( int j = 0 ; j < 7 ; j ++ ) {
            a[ i ].s[ j ] = rand() % 26;
            a[ i ].hs = ( 1ll * a[ i ].hs * b1 + a[ i ].s[ j ] + 1 ) % p1;
        }
    }
    qsort( a , MAXN , sizeof( a[ 1 ] ) , cmp );

    for( int i = 1 ; i < MAXN ; i ++ ) if( a[ i ].hs == a[ i + 1 ].hs ) {
        int f = 0;
        for( int j = 0 ; j < 7 ; j ++ ) f |= a[ i ].s[ j ] != a[ i + 1 ].s[ j ];
        if( f ) {
            for( int j = 0 ; j < 7 ; j ++ ) {
                s[ 0 ][ j ] = a[ i ].s[ j ];
                hs[ 0 ] = ( 1ll * hs[ 0 ] * b2 + s[ 0 ][ j ] + 1 ) % p2;
                s[ 1 ][ j ] = a[ i + 1 ].s[ j ];
                hs[ 1 ] = ( 1ll * hs[ 1 ] * b2 + s[ 1 ][ j ] + 1 ) % p2;
            }
            break;
        }
    }

    // printf("!%d %d\n", hs[ 0 ] , hs[ 1 ] );
    int bp = 1ll * b2 * b2 % p2 * b2 % p2 * b2 % p2 * b2 % p2 * b2 % p2 * b2 % p2;
    for( int i = 1 ; i <= MAXN ; i ++ ) {
        for( int j = 0 ; j < 32 ; j ++ ) {
            b[ i ].s[ j ] = rand() % 2;
            b[ i ].hs = ( 1ll * b[ i ].hs * bp + hs[ b[ i ].s[ j ] ] ) % p2;
        }
    }
    qsort( b , MAXN , sizeof( b[ 1 ] ) , cmp );

    for( int i = 1 ; i < MAXN ; i ++ ) if( b[ i ].hs == b[ i + 1 ].hs ) {
        int f = 0;
        for( int j = 0 ; j < 32 ; j ++ ) f |= b[ i ].s[ j ] != b[ i + 1 ].s[ j ];
        if( f ) {
            for( int j = 0 ; j < 32 ; j ++ )
                for( int k = 0 ; k < 7 ; k ++ )
                    putchar( s[ b[ i ].s[ j ] ][ k ] + 'a' );
            putchar('\n');
            for( int j = 0 ; j < 32 ; j ++ )
                for( int k = 0 ; k < 7 ; k ++ )
                    putchar( s[ b[ i + 1 ].s[ j ] ][ k ] + 'a' );
            return 0;
        }
    }
    assert( 0 );
    return 0;
}