src/str/kmp/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // @return nxt of pattern | ||
| 8 | 96 | inline veci kmp_nxt(strnv pattern) NE { | |
| 9 | 96 | ci32 n = (i32)pattern.size(); | |
| 10 | 96 | veci nxt((u32)n); | |
| 11 | i32 i, j; | ||
| 12 | #pragma GCC diagnostic ignored "-Wsign-conversion" | ||
| 13 |
2/2✓ Branch 2 taken 113998 times.
✓ Branch 3 taken 96 times.
|
114094 | for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) { |
| 14 |
6/6✓ Branch 1 taken 97641 times.
✓ Branch 2 taken 56825 times.
✓ Branch 5 taken 40468 times.
✓ Branch 6 taken 57173 times.
✓ Branch 7 taken 40468 times.
✓ Branch 8 taken 113998 times.
|
154466 | while (~j && pattern[j + 1] != pattern[i]) j = nxt[j]; |
| 15 |
2/2✓ Branch 2 taken 63287 times.
✓ Branch 3 taken 50711 times.
|
113998 | if (pattern[j + 1] == pattern[i]) ++j; |
| 16 | } | ||
| 17 | #pragma GCC diagnostic warning "-Wsign-conversion" | ||
| 18 | 96 | return nxt; | |
| 19 | } | ||
| 20 | |||
| 21 | // find pattern in text | ||
| 22 | // @return matched position in s | ||
| 23 | 96 | inline vecu kmp(strnv pattern, strnv text) NE { | |
| 24 | 96 | veci nxt = kmp_nxt(pattern); | |
| 25 | 96 | vecu ret; | |
| 26 | 96 | ci32 n = (i32)pattern.size(), m = (i32)text.size(); | |
| 27 | i32 i, j; | ||
| 28 | #pragma GCC diagnostic ignored "-Wsign-conversion" | ||
| 29 |
2/2✓ Branch 0 taken 16350957 times.
✓ Branch 1 taken 96 times.
|
16351053 | for (j = -1, i = 0; i < m; ++i) { |
| 30 |
6/6✓ Branch 1 taken 17555860 times.
✓ Branch 2 taken 4512088 times.
✓ Branch 5 taken 5716991 times.
✓ Branch 6 taken 11838869 times.
✓ Branch 7 taken 5716991 times.
✓ Branch 8 taken 16350957 times.
|
22067948 | while (~j && pattern[j + 1] != text[i]) j = nxt[j]; |
| 31 |
2/2✓ Branch 2 taken 12552656 times.
✓ Branch 3 taken 3798301 times.
|
16350957 | if (pattern[j + 1] == text[i]) ++j; |
| 32 |
2/2✓ Branch 0 taken 1990277 times.
✓ Branch 1 taken 14360680 times.
|
16350957 | if (j == n - 1) ret.push_back(i - n + 1), j = nxt[j]; |
| 33 | } | ||
| 34 | #pragma GCC diagnostic warning "-Wsign-conversion" | ||
| 35 | 96 | return ret; | |
| 36 | 96 | } | |
| 37 | |||
| 38 | } // namespace tifa_libs | ||
| 39 |