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ć:
t0*Rm-1+t1*Rm-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;
}