i am trying to write a program that searches through a movie script using two different string searching algorithms. However the Warning C26451: Arithmetic overflow using operator '+' on a 4 byte value then casting the result to 8 byte value keeps on coming up in the calculate hash part of the rabin karp, is there anyway to fix this? Any help would be greatly appreciated.
#define d 256
Position rabinkarp(const string& pat, const string& text) {
int M = pat.size();
int N = text.size();
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
int q = 101;
// The value of h would be "pow(d, M-1)%q"
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
// Calculate the hash value of pattern and first
// window of text
for (i = 0; i < M; i++)
{
p = (d * p + pat[i]) % q;
t = (d * t + text[i]) % q;
}
// Slide the pattern over text one by one
for (i = 0; i <= N - M; i++)
{
// Check the hash values of current window of text
// and pattern. If the hash values match then only
// check for characters on by one
if (p == t)
{
/* Check for characters one by one */
for (j = 0; j < M; j++)
{
if (text[i + j] != pat[j])
break;
}
// if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
if (j == M)
return i;
}
// Calculate hash value for next window of text: Remove
// leading digit, add trailing digit
if (i < N - M)
{
t = (d * (t - text[i] * h) + text[i + M]) % q;// <---- warning is here
[i + M
// We might get negative value of t, converting it
// to positive
if (t < 0)
t = (t + q);
}
}
return -1;
}
You're adding two int
which is 4 bytes in your case, whereas std::string::size_type
is probably 8 bytes in your case. Said conversion happens when you do:
text[i + M]
Which is a call to std::string::operator[]
taking a std::string::size_type
as parameter.
Use std::string::size_type
, which is usually the same as size_t
.
gcc does not give any warning for that, even with -Wall -Wextra -pedantic
, so I guess you activated really every warning you can, or something similar