c++

#include <iostream>
#include <string>

void computeTemporaryArray();
bool KMP();

int lps[1000];
char pattern[1000];
char text[1000];
int lengthOfPattern;
int lengthOfStr;

int main(){
    printf("hi\n");

    char str[]="abcxabcdabcdabcy";
    char subString[]="abcdabcy";

    //sizeof(subString)-1  == 總包含字元數
    //
    memcpy(pattern,subString,sizeof(subString));
    memcpy(text,str,sizeof(str));

    lengthOfStr=sizeof(str)-1;
    lengthOfPattern=sizeof(subString)-1;


    bool a = KMP();

    printf("%lu\n",sizeof(pattern));
    printf("%s\n",pattern);
    if(a){
        printf("suc!\n");
    }
    else{
        printf("false!\n");
    }

    //bool result=KMP(str,subString);

    return 0;
}
//計算失敗函數
void computeTemporaryArray(){
        int index =0;
        for(int i=1; i < lengthOfPattern;){
            if(pattern[i] == pattern[index]){
                lps[i] = index + 1;
                index++;
                i++;
            }else{
                if(index != 0){
                    index = lps[index-1];
                }else{
                    lps[i] =0;
                    i++;
                }
            }
        }
}
/**
 * KMP algorithm of pattern matching.
*/
bool KMP(){
    computeTemporaryArray();
    int i=0;
  int j=0;
  while(i < lengthOfStr && j < lengthOfPattern){
      if(text[i] == pattern[j]){
        i++;
      j++;
    }else{
        if(j!=0){
          j = lps[j-1];
      }else{
          i++;
      }
    }
  }
  if(j == lengthOfPattern){
      return true;
  }
  return false;
}