Substring_index
| 388 | |
| 389 | // Substring_index |
| 390 | GDV_FORCE_INLINE |
| 391 | const char* gdv_fn_substring_index(int64_t context, const char* txt, int32_t txt_len, |
| 392 | const char* pat, int32_t pat_len, int32_t cnt, |
| 393 | int32_t* out_len) { |
| 394 | if (txt_len == 0 || pat_len == 0 || cnt == 0) { |
| 395 | *out_len = 0; |
| 396 | return ""; |
| 397 | } |
| 398 | |
| 399 | if (ARROW_PREDICT_FALSE(txt_len < 0)) { |
| 400 | gdv_fn_context_set_error_msg(context, "Input string length cannot be negative"); |
| 401 | *out_len = 0; |
| 402 | return ""; |
| 403 | } |
| 404 | if (ARROW_PREDICT_FALSE(pat_len < 0)) { |
| 405 | gdv_fn_context_set_error_msg(context, "Pattern string length cannot be negative"); |
| 406 | *out_len = 0; |
| 407 | return ""; |
| 408 | } |
| 409 | |
| 410 | char* out = reinterpret_cast<char*>(gdv_fn_context_arena_malloc(context, txt_len)); |
| 411 | if (out == nullptr) { |
| 412 | gdv_fn_context_set_error_msg(context, "Could not allocate memory for output string"); |
| 413 | *out_len = 0; |
| 414 | return ""; |
| 415 | } |
| 416 | |
| 417 | std::vector<int> lps(pat_len); |
| 418 | int len = 0; |
| 419 | |
| 420 | lps[0] = 0; // lps[0] is always 0 |
| 421 | |
| 422 | // the loop calculates lps[i] for i = 1 to M-1 |
| 423 | int i = 1; |
| 424 | while (i < pat_len) { |
| 425 | if (pat[i] == pat[len]) { |
| 426 | len++; |
| 427 | lps[i] = len; |
| 428 | i++; |
| 429 | } else { |
| 430 | // (pat[i] != pat[len]) |
| 431 | // This is tricky. Consider the example. |
| 432 | // AAACAAAA and i = 7. The idea is similar |
| 433 | // to search step. |
| 434 | if (len != 0) { |
| 435 | len = lps[len - 1]; |
| 436 | |
| 437 | // Also, note that we do not increment |
| 438 | // i here |
| 439 | } else { |
| 440 | // if (len == 0) |
| 441 | lps[i] = 0; |
| 442 | i++; |
| 443 | } |
| 444 | } |
| 445 | } |
| 446 | |
| 447 | std::vector<int> occ; |