#include #include using namespace std; template size_t init(T **r) { *r = (T *)malloc(sizeof(T) * 3); return 3; } template size_t put(T **arr, T el, size_t i, size_t cap) { if (i == cap) *arr = (T *)realloc(*arr, sizeof(T) * (cap *= 2)); (*arr)[i] = el; return cap; } template void end(T **arr, size_t len) { *arr = (T *)realloc(*arr, sizeof(T) * len); } size_t * pfx_tbl(const char *ptrn, size_t &pl) { if (ptrn[0] == '\0') throw 1; size_t *tbl; size_t cap = init(&tbl); tbl[0] = 0; size_t i = 1; for (; ptrn[i] != '\0'; i++) { const char &c = ptrn[i]; size_t ppfx = tbl[i - 1]; char m = ptrn[ppfx]; while (ppfx != 0 && m != c) { ppfx = tbl[ppfx - 1]; m = ptrn[ppfx]; } if (m == c) ppfx++; cap = put(&tbl, ppfx, i, cap); } end(&tbl, i); pl = i; return tbl; } template void print(T *c, size_t len) { if (len == 0) return; cout << "[ "; for (size_t i = 0; i < len - 1; i++) { cout << c[i] << ", "; } cout << c[len - 1] << " ]" << endl; } size_t kmpfi(size_t *tbl, const char *s, const char *p) { size_t pi, si, mfi; pi = si = mfi = 0; for (; s[si] != '\0';) { if (s[si] == p[pi]) { if (p[pi + 1] == '\0') return mfi; else { si++; pi++; } } else { if (pi == 0) mfi = ++si; else { pi = tbl[pi - 1]; mfi = si - pi; } } } return -1; } void strsplit(const char *s, const char *p, char ***r, size_t &len, bool ree) { size_t rcap = init(r); size_t ri, si, mi; ri = si = mi = 0; size_t pl; size_t *tbl = pfx_tbl(p, pl); while ((mi = kmpfi(tbl, s + si, p)) != string::npos) { mi = si + mi; if (si == mi && ree) continue; rcap = put(r, (char *)malloc(sizeof(char) * (mi - si + 1)), ri, rcap); memcpy((*r)[ri], s + si, (mi - si) * sizeof(char)); (*r)[ri][mi - si] = '\0'; si = pl + mi; ri++; } if (s[si] != '\0') { char *lr; size_t lrcap = init(&lr); size_t lri = 0; do lrcap = put(&lr, s[si++], lri++, lrcap); while (s[si - 1] != '\0'); end(&lr, lri); rcap = put(r, lr, ri++, rcap); } len = ri; end(r, ri); free(tbl); } int main() { cout << "Input string: abgeezusabrekabstyleabmuhaha" << endl; const char *s = "abgeezusabrekabstyleabmuhaha"; const char *p = "ab"; size_t len; char **r; strsplit(s, p, &r, len, false); cout << "Substrings: " << endl; cout << "[ "; for (size_t i = 0; i < len - 1; i++) { size_t si = 0; while (r[i][si] != '\0') { cout << r[i][si]; si++; } cout << ", "; } size_t si = 0; while (r[len - 1][si] != '\0') { cout << r[len - 1][si]; si++; } cout << " ]" << endl; return 0; }

Linear time KMP string split