Code:
#include <iostream>
#include <cstring>
#include <string.h>
using namespace std;
#define MOD 31
int hash(char* a, int n)
{
// Hash function is computed by adding all the characters and
// taking remainder by MOD.
int i;
int sum = 0;
for(i = 0; i < n; i++)
sum += *a++;
return (sum % MOD);
}
int incremental_hash(int oldhash, char outgoing, char incoming)
{
int inchash = oldhash - outgoing + incoming;
return (inchash % MOD);
}
int match(char* a, int m, char* s, int n)
{
// Compare s to substrings of length n. Return position if match is found, -1 else.
// Strategy: Compute the hash of s. Compare that hash to the hash of the first n
// positions in a. If equal, carry out a full character-by-character comparison (use
// memcmp) to determine if s occurs in a. If no match, try the next substring in a.
// Compute the new hash from the old hash by subtracting to the old hash the first character
// of the prior substring and adding the last character of the new substring.
int x, y;
int i = 0;
x = hash(s,n);
y = hash(a,n);
if((x == y) && (memcmp(a, s, n) == 0))
return 0;
else{
for(i = 1; i <= (m-n); ++i){
y = incremental_hash(y, a[i-1], a[i+n-1]);
if((x == y) && (memcmp(i+a, s, n) == 0))
return i;
}
}
return -1;
}
int main()
{
// Test.
char ASC[NULL];
ASC[0,0] = 'char'; ASC[0,1] = 'ASCII'; ASC[0,2] = ' '; ASC[0,3] = 'char'; ASC[0,4] = 'ASCII'; ASC[0,5] = ' '; ASC[0,6] = 'char'; ASC[0,7] = 'ASCII';
ASC[1,0] = 'A'; ASC[1,1] = '65'; ASC[1,2] = ' '; ASC[1,3] = 'a'; ASC[1,4] = '97'; ASC[1,5] = ' '; ASC[1,6] = '0'; ASC[1,7] = '48';
ASC[2,0] = 'B'; ASC[2,1] = '66'; ASC[2,2] = ' '; ASC[2,3] = 'b'; ASC[2,4] = '98'; ASC[2,5] = ' '; ASC[2,6] = '1'; ASC[2,7] = '49';
ASC[3,0] = 'C'; ASC[3,1] = '67'; ASC[3,2] = ' '; ASC[3,3] = 'c'; ASC[3,4] = '99'; ASC[3,5] = ' '; ASC[3,6] = '2'; ASC[3,7] = '50';
ASC[4,0] = 'D'; ASC[4,1] = '68'; ASC[4,2] = ' '; ASC[4,3] = 'd'; ASC[4,4] = '100'; ASC[4,5] = ' '; ASC[4,6] = '3'; ASC[4,7] = '51';
ASC[5,0] = 'E'; ASC[5,1] = '69'; ASC[5,2] = ' '; ASC[5,3] = 'e'; ASC[5,4] = '101'; ASC[5,5] = ' '; ASC[5,6] = '4'; ASC[5,7] = '52';
ASC[6,0] = 'F'; ASC[5,1] = '70'; ASC[6,2] = ' '; ASC[6,3] = 'f'; ASC[6,4] = '102'; ASC[6,5] = ' '; ASC[6,6] = '5'; ASC[6,7] = '53';
ASC[7,0] = 'G'; ASC[5,1] = '71'; ASC[7,2] = ' '; ASC[7,3] = 'g'; ASC[7,4] = '103'; ASC[7,5] = ' '; ASC[7,6] = '6'; ASC[7,7] = '54';
ASC[8,0] = 'H'; ASC[5,1] = '72'; ASC[8,2] = ' '; ASC[8,3] = 'h'; ASC[8,4] = '104'; ASC[8,5] = ' '; ASC[8,6] = '7'; ASC[8,7] = '55';
ASC[9,0] = 'I'; ASC[5,1] = '73'; ASC[9,2] = ' '; ASC[9,3] = 'i'; ASC[9,4] = '105'; ASC[9,5] = ' '; ASC[9,6] = '8'; ASC[9,7] = '56';
ASC[10,0] = 'J'; ASC[5,1] = '74'; ASC[10,2] = ' ';ASC[10,3] = 'j'; ASC[10,4] = '106'; ASC[10,5] = ' ';ASC[10,6] = '9'; ASC[10,7] = '57';
ASC[11,0] = 'K'; ASC[5,1] = '75'; ASC[11,2] = ' ';ASC[11,3] = 'k'; ASC[11,4] = '107'; ASC[11,5] = ' ';ASC[11,6] = ' '; ASC[11,7] = ' ';
ASC[12,0] = 'L'; ASC[5,1] = '76'; ASC[12,2] = ' ';ASC[12,3] = 'l'; ASC[12,4] = '108'; ASC[12,5] = ' ';ASC[12,6] = ' '; ASC[12,7] = ' ';
ASC[13,0] = 'M'; ASC[5,1] = '77'; ASC[13,2] = ' ';ASC[13,3] = 'm'; ASC[13,4] = '109'; ASC[13,5] = ' ';ASC[13,6] = ' '; ASC[13,7] = ' ';
ASC[14,0] = 'N'; ASC[5,1] = '78'; ASC[14,2] = ' ';ASC[14,3] = 'n'; ASC[14,4] = '110'; ASC[14,5] = ' ';ASC[14,6] = ' '; ASC[14,7] = ' ';
ASC[15,0] = 'O'; ASC[5,1] = '79'; ASC[15,2] = ' ';ASC[15,3] = 'o'; ASC[15,4] = '111'; ASC[15,5] = ' ';ASC[15,6] = ' '; ASC[15,7] = ' ';
ASC[16,0] = 'P'; ASC[5,1] = '80'; ASC[16,2] = ' ';ASC[16,3] = 'p'; ASC[16,4] = '112'; ASC[16,5] = ' ';ASC[16,6] = ' '; ASC[16,7] = ' ';
ASC[17,0] = 'Q'; ASC[5,1] = '81'; ASC[17,2] = ' ';ASC[17,3] = 'q'; ASC[17,4] = '113'; ASC[17,5] = ' ';ASC[17,6] = ' '; ASC[17,7] = ' ';
ASC[18,0] = 'R'; ASC[5,1] = '82'; ASC[18,2] = ' ';ASC[18,3] = 'r'; ASC[18,4] = '114'; ASC[18,5] = ' ';ASC[18,6] = ' '; ASC[18,7] = ' ';
ASC[19,0] = 'S'; ASC[5,1] = '83'; ASC[19,2] = ' ';ASC[19,3] = 's'; ASC[19,4] = '115'; ASC[19,5] = ' ';ASC[19,6] = ' '; ASC[19,7] = ' ';
ASC[20,0] = 'T'; ASC[5,1] = '84'; ASC[20,2] = ' ';ASC[20,3] = 't'; ASC[20,4] = '116'; ASC[20,5] = ' ';ASC[20,6] = ' '; ASC[20,7] = ' ';
ASC[21,0] = 'U'; ASC[5,1] = '85'; ASC[21,2] = ' ';ASC[21,3] = 'u'; ASC[21,4] = '117'; ASC[21,5] = ' ';ASC[21,6] = ' '; ASC[21,7] = ' ';
ASC[22,0] = 'V'; ASC[5,1] = '86'; ASC[22,2] = ' ';ASC[22,3] = 'v'; ASC[22,4] = '118'; ASC[22,5] = ' ';ASC[22,6] = ' '; ASC[22,7] = ' ';
ASC[23,0] = 'W'; ASC[5,1] = '87'; ASC[23,2] = ' ';ASC[23,3] = 'w'; ASC[23,4] = '119'; ASC[23,5] = ' ';ASC[23,6] = ' '; ASC[23,7] = ' ';
ASC[24,0] = 'X'; ASC[5,1] = '88'; ASC[24,2] = ' ';ASC[24,3] = 'x'; ASC[24,4] = '120'; ASC[24,5] = ' ';ASC[24,6] = ' '; ASC[24,7] = ' ';
ASC[25,0] = 'Y'; ASC[5,1] = '89'; ASC[25,2] = ' ';ASC[25,3] = 'y'; ASC[25,4] = '121'; ASC[25,5] = ' ';ASC[25,6] = ' '; ASC[25,7] = ' ';
ASC[26,0] = 'Z'; ASC[5,1] = '90'; ASC[26,2] = ' ';ASC[26,3] = 'z'; ASC[26,4] = '122'; ASC[26,5] = ' ';ASC[26,6] = ' '; ASC[26,7] = ' ';
cout << "This is the ASCII table:\n";
cout << &ASC << endl;
cout << "\nEnter values to array A:\n";
int i;
int n = 0;
char A[NULL];
while(cin >> i){
A[n] = i;
n++;
}
cin.clear();
cout << "\nEnter values to array B:\n";
int j;
int m = 0;
char B[NULL];
while(cin >> j){
B[m] = j;
m++;
}
int Q;
Q = match(A, n+1, B, m+1);
if(Q == -1)
cout << "\nNOT FOUND!";
else
cout << "\nFOUND AT POSSITION:" << Q;
return 0;
}