2

I wrote a KMP sub-string search program in C++. The compilation is oK but the result is not the same as I expected. My code is

class Solution {
public:
  static int kmpSearch(const string& s, const string& p){

    int* next = new int[p.length()];
    getNext(p, next);
    int i=0;
    int j=0;
    while(i<s.length() && j<p.length()){
      if(j==-1 || s.at(i) == p.at(j)){
        i++; j++;
      }else{
        j=next[j];
      }
    }

    delete next;
    if(j==p.length())  return i-j;
    else return -1;

  }



  static void getNext(string p, int* next){
    int len = p.length();

    next[0] =-1;
    int j=0;

    int k=-1;

    while(j<len-1){
      if(k==-1 || p[j]==p[k]){
        j++;
        k++;
        next[j]=k;
      }else{
        k=next[k];
      }
    }

  }
};


int main(int argc, char* argv[]){
  string s(argv[1]);
  string p(argv[2]);
  int loc = Solution::kmpSearch(s, p);
  std::cout<<" the location is "<< s << "  "<< p<< " " <<loc<< std::endl;
}

I used GDB to debug and something strange at condition while(i<s.length() && j<p.length()) in method kmpSearch. Here is my GDB debug output.

(gdb) l
9   
10      int* next = new int[p.length()];
11      getNext(p, next);
12      int i=0;
13      int j=0;
14      while(i<s.length() && j<p.length()){
15        if(j==-1 || s.at(i) == p.at(j)){
16          i++; j++;
17        }else{
18          j=next[j];
(gdb) p j
$24 = -1
(gdb) p p.length()
$25 = 3
(gdb) p j<p.length()
$26 = false
(gdb)

Parameters are shijie jie. The strange thing is in line 14 that p j<p.length() should be true, as the j =-1 and p.length is 3, but it prints false

shijie xu
  • 1,975
  • 21
  • 52
  • string::length is size_t which is unsigned. I imagine that j which is -1 is being converted to an unsigned int before the comparison which results in a very large number due to wrap around. I am more of a C developer, but you should cast p.length to a signed integer before doing the comparison. – Elias Dec 07 '16 at 01:18
  • 2
    Possible duplicate of [Signed/unsigned comparisons](http://stackoverflow.com/questions/5416414/signed-unsigned-comparisons) – The Dark Dec 07 '16 at 01:20
  • 1
    Didn't your compiler warn you about signed / unsigned variables being used on that line? – PaulMcKenzie Dec 07 '16 at 01:21
  • 1
    Also, you should be using `delete[] next;` – qxz Dec 07 '16 at 01:24
  • Thanks. I use command `g++ -o kmp kmp.cpp` and it does not give any warn. It is negative and size_t comparison issue and fixed now.. – shijie xu Dec 07 '16 at 01:26
  • @shijiexu Use `-Wall` when compiling your program [as seen here](http://rextester.com/UYOQG53711) – PaulMcKenzie Dec 07 '16 at 01:34

0 Answers0