Witam, czy mógłby ktoś wytłumaczyć zastosowanie algorytmu Rabina-Karpa przy wyszukiwaniu wzorca w tablicy dwuwymiarowej? ( chciałbym użyć go do zadania: http://ki.staszic.waw.pl/task.php?name=litery ).

Na razie doszedłem do:
W przypadku jednowymiarowym hash słowa o długości m przyjmuje postać:
t0Rm-1+t1Rm-2+...+tm-1*R0
gdzie R to liczba pierwsza, a ti to kolejne litery naszego słowa.
Czyli wykładniki liczby R stojące przy kolejnych literach słowa, którego m = 5 to:
4 3 2 1 0

W przypadku dwuwymiarowym gdzie wzorzec ma wymiary na przykład 3 x 3 wykładniki liczby R przy kolejnych literach wzorca to:
4 3 2
3 2 1
2 1 0

Jednakże przy zastosowaniu takiego hashowania litery na kolejnych przekątnych wzorca mogą być pomieszane, a uzyskane hashe będą takie same to znaczy:

aaA
aBa
Caa

oraz

aaB
aCa
Aaa

mają indentyczne hashe. Czy da się rozwiązać ten problem?

Oto mój dotychczasowy kod:


#include<iostream>
using namespace std;

long long mod = 1000000009 , x = 313;
char c;
int n , m ,res;
int p[ 1000010 ];
long long h[ 1010 ][ 1010 ];
long long h2[ 1010 ][ 1010 ];
char t[ 1010 ][ 1010 ];
char t2[ 1010 ][ 1010 ];
long long M( long long h )
{
    return ((h % mod) + mod)% mod;
}
int Level( int i , int j )
{
    return i + j - 1;
}
long long Hash( int x1 , int y1 , int x2 , int y2 )
{
    long long hash = h[ x1 ][ y1 ]
    - h[ x1 ][ y2 - 1 ] * p[ Level( x1 , y1 ) - Level( x1 , y2 - 1 ) ]
    - h[ x2 - 1 ][ y1 ] * p[ Level( x1 , y1 ) - Level( x2 - 1, y1 ) ]
    + h[ x2 - 1 ][ y2 - 1 ] * p[ Level( x1 , y1 ) - Level( x2 - 1, y2 - 1 ) ];
    return M( hash );
}

int main()
{
    ios_base::sync_with_stdio( 0 );
    cin >> n >> m;
    p[ 0 ] = 1;
    for( int i = 1 ; i <= n * n + 1 ; i++ ) p[ i ] = ( p[ i - 1 ] * x ) % mod;

    for( int i = 1 ; i <= n ; i++ )
    {
        for( int j = 1 ; j <= n ; j++ )
        {
            cin >> c;
            h[ i ][ j ] = M(( h[ i - 1 ][ j ] + h[ i ][ j - 1 ] ) * x - h[ i - 1 ][ j - 1 ] * x * x + c );
            t[ i ][ j ] = c;
        }
    }
    for( int i = 1 ; i <= m ; i++ )
    {
        for( int j = 1 ; j <= m ; j++ )
        {
            cin >> c;
            h2[ i ][ j ] = M(( h2[ i - 1 ][ j ] + h2[ i ][ j - 1 ] ) * x - h2[ i - 1 ][ j - 1 ] * x * x + c );
            t2[ i ][ j ] = c;
        }
    }

    for( int i = m ; i <= n ; i++ )
    {
        for( int j = m ; j <= n ; j++ )
        {

            if( M( Hash( i , j , i - m + 1 , j - m + 1 )) == M(h2[ m ][ m ]) )
            {
                bool good = true;
                for( int k = 0 ; k < m ; k++ )
                {
                    for( int l = 0 ; l < m ; l++ )
                    {
                        if( t[ i - k ][ j - l ] != t2[ m- k ][ m - l ] )
                        {
                            good =false;
                            break;
                        }
                    }
                    if( !good ) break;
                }

                if( good )
                    res++;
            }
        }
    }
    cout << res;
}