String Processing/Suffix Trie, Tree, Array/760.cpp
// string matching in O(m log n)
string matching in O(m log n)
string matching in O ( m log n )
ii stringMatching() {
    int lo = 0, hi = n-1, mid = lo;
    while (lo < hi) {
        mid = (lo + hi) / 2;
        int res = strncmp(T + SA[mid], P, m);
        if (res >= 0) hi = mid;
        else lo = mid + 1;
    }
    if (strncmp(T + SA[lo], P, m) != 0) return ii(-1, -1);
    ii ans; ans.first = lo;
    lo = 0; hi = n - 1; mid = lo;
    while (lo < hi) {
        mid = (lo + hi) / 2;
        int res = strncmp(T + SA[mid], P, m);
        if (res > 0) hi = mid;
        else lo = mid + 1;
    }
    if (strncmp(T + SA[hi], P, m) != 0) hi--;
    ans.second = hi;
    return ans;
}
ii stringMatching ( ) { int lo = 0 , hi = n - 1 , mid = lo ; while ( lo < hi ) { mid = ( lo + hi ) / 2 ; int res = strncmp ( T + SA [ mid ] , P , m ) ; if ( res >= 0 ) hi = mid ; else lo = mid + 1 ; } if ( strncmp ( T + SA [ lo ] , P , m ) != 0 ) return ii ( -1 , -1 ) ; ii ans ; ans . first = lo ; lo = 0 ; hi = n - 1 ; mid = lo ; while ( lo < hi ) { mid = ( lo + hi ) / 2 ; int res = strncmp ( T + SA [ mid ] , P , m ) ; if ( res > 0 ) hi = mid ; else lo = mid + 1 ; } if ( strncmp ( T + SA [ hi ] , P , m ) != 0 ) hi -- ; ans . second = hi ; return ans ; }
string matching in O(m log n)
string matching in O ( m log n )