The goal of this assignment is to master the technical details of updating a “sliding window hash” in an array.

**First Task:** Storing the Input in an Array of Integers

**Second Task:** Counting Symmetries the Slow Way Please write code that counts the total number of symmetries in the way we just described; that is, For every index, i = 1, 2, 3, ...Determine if the entire array starting at index 0matches the entire array starting at index i (wrapping around as appropriate). Stop at the first such index i that is a match. Output the array length divided by i.

**Third Task:** Counting Symmetries Faster with Hashing We can make our algorithm faster as follows: Let H be a polynomial hash of the entire array, starting at index 0For every index i = 1, 2, 3, ...Let H’ be the updated hash for the entire array, starting at index iIf H == H’, then check to see if there is actually a match at index i. Stop at the first such index i that is a match. Output the array length divided by i. The slow.cpp will contain the code for the non-hashing and the fast.cpp contains the hashing.

**Solution:**

**
**

```
#include < iostream>
using namespace std;
int compute_hash(const int n, const int start, const int x, const int p, const int* A) {
int H = 0;
for ( int i = 0; i < n; i++ ) {
H = (int)( ( (long long)H * x + A[( start + i ) % n] ) % p );
}
return H;
}
int main( int argc, char** argv ) {
int *A;
int *B;
int i, j, k;
char cmd;
int value;
int match;
int H, H_dash;
int seed = 13;
int p = 1000000007;
int tmp;
// First Task: Storing the Input in an Array of Integers
cin >> k;
A = new int[ 2 * k ];
j = 0;
for ( i = 0; i < k; i++ ) {
cin >> cmd >> value;
switch ( cmd ) {
case 'F':
A[j++] = 0;
break;
case 'L':
A[j++] = 1;
break;
case 'R':
A[j++] = 2;
break;
default:
break;
}
A[j++] = value;
}
// Second Task: Counting Symmetries the Slow Way
// For every index i = 1, 2, 3, ...
for ( i = 1; i < k; i++ ) {
match = 1;
// Determine if the entire array starting at index 0
// matches the entire array starting at index i (wrapping around as appropriate).
for ( j = 0; j < k; j++ ) {
if ( ( A[( 2 * ( i + j ) ) % ( 2 * k )] != A[2 * j] ) ||
( A[( 2 * ( i + j ) + 1 ) % ( 2 * k )] != A[2 * j + 1] ) ) {
match = 0;
break;
}
}
// Stop at the first such index i that is a match.
if ( match == 1 ) {
break;
}
}
// Output the array length divided by i
cout << ( k / i ) << endl;
return 0;
}
// Third Task: Counting Symmetries Faster with Hashing
// Let H be a polynomial hash of the entire array, starting at index 0
H = compute_hash( 2 * k, 0, seed, p, A );
B = new int[2 * k];
B[0] = seed % p;
for ( i = 1; i < 2 * k; i++ ) {
// x^n % p = ( ( x^(n - 1) % p ) * ( x % p ) ) % p;
B[i] = ( (long long)B[i - 1] * ( seed % p ) ) % p;
}
// For every index i = 1, 2, 3, ...
tmp = A[0] % p;
H_dash = ( (long long)( ( p + ( H % p ) - ( ( (long long)tmp * B[2 * k - 2] ) % p ) ) % p ) * ( seed % p ) ) % p + tmp;
for ( i = 1; i < k; i++ ) {
// Let H' be the updated hash for the entire array, starting at index i
// H' = ((H - A[i] x^(n - 1)) x + A[i]) % p
// => H' = ((H - A[i] x^(n - 1)) x) % p + A[i] % p
// => H' = ( ((H - A[i] x^(n - 1)) % p) (x % p) ) % p + A[i] %p
// => H' = ( ( p + H % p - ( ( A[i] % p ) ( x^(n - 1) % p ) % p ) ) % p ) * ( x % p ) % p + A[i] % p
tmp = A[2 * i - 1] % p;
H_dash = ( (long long)( ( p + ( H_dash % p ) - ( ( (long long)tmp * B[2 * k - 2] ) % p ) ) % p ) * ( seed % p ) ) % p + tmp;
// If H == H', then check to see if there is actually a match at index i.
if ( H == H_dash ) {
match = 1;
// Determine if the entire array starting at index 0
// matches the entire array starting at index i (wrapping around as appropriate).
for ( j = 0; j < k; j++ ) {
if ( ( A[( 2 * ( i + j ) ) % ( 2 * k )] != A[2 * j] ) ||
( A[( 2 * ( i + j ) + 1 ) % ( 2 * k )] != A[2 * j + 1] ) ) {
match = 0;
break;
}
}
// Stop at the first such index i that is a match.
if ( match == 1 ) {
break;
}
}
tmp = A[2 * i] % p;
H_dash = ( (long long)( ( p + ( H_dash % p ) - ( ( (long long)tmp * B[2 * k - 2] ) % p ) ) % p ) * ( seed % p ) ) % p + tmp;
}
// Output the array length divided by i
cout << ( k / i ) << endl;
return 0;
}
```