题解 | #字串比较# 最优解？

I题，线性时间构造，常量时间查询。 最优解？

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define out(x) cout << #x << '=' << (x) << endl
#define out2(x, y) cout << #x << '=' << (x) << ',' << #y << '=' << (y) << endl 
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))

using namespace std;

using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

template<typename T> ostream & operator << (ostream &out,const set<T>&obj){out<<"set(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<*it;out<<")";return out;}
template<typename T1,typename T2> ostream & operator << (ostream &out,const map<T1,T2>&obj){out<<"map(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<it->first<<": "<<it->second;out<<")";return out;}
template<typename T1,typename T2> ostream & operator << (ostream &out,const pair<T1,T2>&obj){out<<"<"<<obj.first<<", "<<obj.second<<">";return out;}
template<typename T> ostream & operator << (ostream &out,const vector<T>&obj){out<<"vector(";for(auto it=obj.begin();it!=obj.end();it++) out<<(it==obj.begin()?"":", ")<<*it;out<<")";return out;}

namespace Fast_IO{ 
    const int MAXL((1 << 18) + 1);int iof, iotp;
    char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55];
    char Getchar(){
        if (ioiS == ioiT){
            ioiS=ioif;ioiT=ioiS+fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++);
        }else return (*ioiS++);
    }
    void Write(){fwrite(ioof,1,iooS-ioof,stdout);iooS=ioof;}
    void Putchar(char x){*iooS++ = x;if (iooS == iooT)Write();}
    inline int read(){
        int x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    inline long long read_ll(){
        long long x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    void Getstr(char *s, int &l){
        for(ioc=Getchar();ioc==' '||ioc=='\n'||ioc=='\t';)ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(l=0;!(ioc==' '||ioc=='\n'||ioc=='\t'||ioc==EOF);ioc=Getchar())s[l++]=ioc;s[l] = 0;
    }
    template <class Int>void Print(Int x, char ch = '\0'){
        if(!x)Putchar('0');if(x<0)Putchar('-'),x=-x;while(x)iost[++iotp]=x%10+'0',x/=10;
        while(iotp)Putchar(iost[iotp--]);if (ch)Putchar(ch);
    }
    void Putstr(const char *s){for(int i=0,n=strlen(s);i<n;++i)Putchar(s[i]);}
} // namespace Fast_IO
using namespace Fast_IO;

namespace SAIS {
#define SAIS_UCHAR_SIZE 256
#define SAIS_MINBUCKETSIZE 256
#define sais_index_type int
#define sais_bool_type int
#define SAIS_LMSSORT2_LIMIT 0x3fffffff
#define SAIS_MYMALLOC(_num, _type) ((_type *)malloc((_num) * sizeof(_type)))
#define chr(_a)                                                   \
    (cs == sizeof(sais_index_type) ? ((sais_index_type *)T)[(_a)] \
                                   : ((unsigned char *)T)[(_a)])
  inline void getCounts(const void *T, sais_index_type *C, sais_index_type n,
                        sais_index_type k, int cs) {
    sais_index_type i;
    for (i = 0; i < k; ++i) C[i] = 0;
    for (i = 0; i < n; ++i) ++C[chr(i)];
  } // getCounts
  inline void getBuckets(const sais_index_type *C, sais_index_type *B,
                         sais_index_type k, sais_bool_type end) {
    sais_index_type i, sum = 0;
    if (end) {
      for (i = 0; i < k; ++i) {
        sum += C[i];
        B[i] = sum;
      }
    } else {
      for (i = 0; i < k; ++i) {
        sum += C[i];
        B[i] = sum - C[i];
      }
    }
  } // getBuckets
  void LMSsort1(const void *T, sais_index_type *SA, sais_index_type *C,
                sais_index_type *B, sais_index_type n, sais_index_type k,
                int cs) {
    sais_index_type *b, i, j;
    sais_index_type c0, c1;
    if (C == B) getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 0);
    j = n - 1;
    b = SA + B[c1 = chr(j)];
    --j;
    *b++ = (chr(j) < c1) ? ~j : j;
    for (i = 0; i < n; ++i) {
      if (0 < (j = SA[i])) {
        if ((c0 = chr(j)) != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        --j;
        *b++ = (chr(j) < c1) ? ~j : j;
        SA[i] = 0;
      } else if (j < 0) SA[i] = ~j;
    }
    if (C == B) getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 1);
    for (i = n - 1, b = SA + B[c1 = 0]; 0 <= i; --i) {
      if (0 < (j = SA[i])) {
        if ((c0 = chr(j)) != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        --j;
        *--b = (chr(j) > c1) ? ~(j + 1) : j;
        SA[i] = 0;
      }
    }
  } // LMSsort1
  sais_index_type LMSpostproc1(const void *T, sais_index_type *SA,
                               sais_index_type n, sais_index_type m,
                               int cs) {
    sais_index_type i, j, p, q, plen, qlen, name;
    sais_index_type c0, c1;
    sais_bool_type diff;
    for (i = 0; (p = SA[i]) < 0; ++i) SA[i] = ~p;
    if (i < m) {
      for (j = i, ++i;; ++i) {
        if ((p = SA[i]) < 0) {
          SA[j++] = ~p;
          SA[i] = 0;
          if (j == m) break;
        }
      }
    }
    i = n - 1;
    j = n - 1;
    c0 = chr(n - 1);
    do c1 = c0;
    while ((0 <= --i) && ((c0 = chr(i)) >= c1));
    for (; 0 <= i;) {
      do c1 = c0;
      while ((0 <= --i) && ((c0 = chr(i)) <= c1));
      if (0 <= i) {
        SA[m + ((i + 1) >> 1)] = j - i;
        j = i + 1;
        do c1 = c0;
        while ((0 <= --i) && ((c0 = chr(i)) >= c1));
      }
    }
    for (i = 0, name = 0, q = n, qlen = 0; i < m; ++i) {
      p = SA[i], plen = SA[m + (p >> 1)], diff = 1;
      if ((plen == qlen) && ((q + plen) < n)) {
        for (j = 0; (j < plen) && (chr(p + j) == chr(q + j)); ++j) ;
        if (j == plen) diff = 0;
      }
      if (diff != 0) ++name, q = p, qlen = plen;
      SA[m + (p >> 1)] = name;
    }
    return name;
  } // LMSpostproc1
  void LMSsort2(const void *T, sais_index_type *SA, sais_index_type *C,
                sais_index_type *B, sais_index_type *D, sais_index_type n,
                sais_index_type k, int cs) {
    sais_index_type *b, i, j, t, d;
    sais_index_type c0, c1;
    getBuckets(C, B, k, 0);
    j = n - 1;
    b = SA + B[c1 = chr(j)];
    --j;
    t = (chr(j) < c1);
    j += n;
    *b++ = (t & 1) ? ~j : j;
    for (i = 0, d = 0; i < n; ++i) {
      if (0 < (j = SA[i])) {
        if (n <= j) d += 1, j -= n;
        if ((c0 = chr(j)) != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        --j;
        t = c0;
        t = (t << 1) | (chr(j) < c1);
        if (D[t] != d) j += n, D[t] = d;
        *b++ = (t & 1) ? ~j : j;
        SA[i] = 0;
      } else if (j < 0) SA[i] = ~j;
    }
    for (i = n - 1; 0 <= i; --i) {
      if (0 < SA[i]) {
        if (SA[i] < n) {
          SA[i] += n;
          for (j = i - 1; SA[j] < n; --j) ;
          SA[j] -= n;
          i = j;
        }
      }
    }
    getBuckets(C, B, k, 1);
    for (i = n - 1, d += 1, b = SA + B[c1 = 0]; 0 <= i; --i) {
      if (0 < (j = SA[i])) {
        if (n <= j) d += 1, j -= n;
        if ((c0 = chr(j)) != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        --j;
        t = c0;
        t = (t << 1) | (chr(j) > c1);
        if (D[t] != d) j += n, D[t] = d;
        *--b = (t & 1) ? ~(j + 1) : j;
        SA[i] = 0;
      }
    }
  } // LMSsort2
  sais_index_type LMSpostproc2(sais_index_type *SA, sais_index_type n, sais_index_type m) {
    sais_index_type i, j, d, name;
    for (i = 0, name = 0; (j = SA[i]) < 0; ++i) {
      j = ~j;
      if (n <= j) name += 1;
      SA[i] = j;
    }
    if (i < m) {
      for (d = i, ++i;; ++i) {
        if ((j = SA[i]) < 0) {
          j = ~j;
          if (n <= j) name += 1;
          SA[d++] = j;
          SA[i] = 0;
          if (d == m) break;
        }
      }
    }
    if (name < m) {
      for (i = m - 1, d = name + 1; 0 <= i; --i) {
        if (n <= (j = SA[i])) j -= n, --d;
        SA[m + (j >> 1)] = d;
      }
    } else {
      for (i = 0; i < m; ++i)
        if (n <= (j = SA[i])) j -= n, SA[i] = j;
    }
    return name;
  } // LMSpostproc2
  void induceSA(const void *T, sais_index_type *SA, sais_index_type *C,
                sais_index_type *B, sais_index_type n, sais_index_type k,
                int cs) {
    sais_index_type *b, i, j;
    sais_index_type c0, c1;
    if (C == B) getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 0);
    j = n - 1;
    b = SA + B[c1 = chr(j)];
    *b++ = ((0 < j) && (chr(j - 1) < c1)) ? ~j : j;
    for (i = 0; i < n; ++i) {
      j = SA[i], SA[i] = ~j;
      if (0 < j) {
        --j;
        if ((c0 = chr(j)) != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        *b++ = ((0 < j) && (chr(j - 1) < c1)) ? ~j : j;
      }
    }
    if (C == B) getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 1);
    for (i = n - 1, b = SA + B[c1 = 0]; 0 <= i; --i) {
      if (0 < (j = SA[i])) {
        --j;
        if ((c0 = chr(j)) != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        *--b = ((j == 0) || (chr(j - 1) > c1)) ? ~j : j;
      } else SA[i] = ~j;
    }
  } // induceSA
  sais_index_type computeBWT(const void *T, sais_index_type *SA,
                             sais_index_type *C, sais_index_type *B,
                             sais_index_type n, sais_index_type k,
                             int cs) {
    sais_index_type *b, i, j, pidx = -1;
    sais_index_type c0, c1;
    if (C == B) getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 0);
    j = n - 1;
    b = SA + B[c1 = chr(j)];
    *b++ = ((0 < j) && (chr(j - 1) < c1)) ? ~j : j;
    for (i = 0; i < n; ++i) {
      if (0 < (j = SA[i])) {
        --j;
        SA[i] = ~((sais_index_type)(c0 = chr(j)));
        if (c0 != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        *b++ = ((0 < j) && (chr(j - 1) < c1)) ? ~j : j;
      } else if (j != 0) SA[i] = ~j;
    }
    if (C == B) getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 1);
    for (i = n - 1, b = SA + B[c1 = 0]; 0 <= i; --i) {
      if (0 < (j = SA[i])) {
        --j;
        SA[i] = (c0 = chr(j));
        if (c0 != c1) {
          B[c1] = b - SA;
          b = SA + B[c1 = c0];
        }
        *--b = ((0 < j) && (chr(j - 1) > c1)) ? ~((sais_index_type)chr(j - 1)) : j;
      } else if (j != 0) SA[i] = ~j;
      else pidx = i;
    }
    return pidx;
  } // computeBWT
  sais_index_type sais_main(const void *T, sais_index_type *SA,
                            sais_index_type fs, sais_index_type n,
                            sais_index_type k, int cs, sais_bool_type isbwt) {
    sais_index_type *C, *B, *D, *RA, *b;
    sais_index_type i, j, m, p, q, t, name, pidx = 0, newfs;
    sais_index_type c0, c1;
    unsigned int flags;
    if (k <= SAIS_MINBUCKETSIZE) {
      if ((C = SAIS_MYMALLOC(k, sais_index_type)) == NULL) return -2;
      if (k <= fs) {
        B = SA + (n + fs - k);
        flags = 1;
      } else {
        if ((B = SAIS_MYMALLOC(k, sais_index_type)) == NULL) {
          free(C);
          return -2;
        }
        flags = 3;
      }
    } else if (k <= fs) {
      C = SA + (n + fs - k);
      if (k <= (fs - k)) {
        B = C - k;
        flags = 0;
      } else if (k <= (SAIS_MINBUCKETSIZE * 4)) {
        if ((B = SAIS_MYMALLOC(k, sais_index_type)) == NULL) return -2;
        flags = 2;
      } else {
        B = C;
        flags = 8;
      }
    } else {
      if ((C = B = SAIS_MYMALLOC(k, sais_index_type)) == NULL) return -2;
      flags = 4 | 8;
    }
    if ((n <= SAIS_LMSSORT2_LIMIT) && (2 <= (n / k))) {
      if (flags & 1) flags |= ((k * 2) <= (fs - k)) ? 32 : 16;
      else if ((flags == 0) && ((k * 2) <= (fs - k * 2))) flags |= 32;
    }
    getCounts(T, C, n, k, cs);
    getBuckets(C, B, k, 1);
    for (i = 0; i < n; ++i) SA[i] = 0;
    b = &t; i = n - 1; j = n; m = 0; c0 = chr(n - 1);
    do c1 = c0;
    while ((0 <= --i) && ((c0 = chr(i)) >= c1));
    for (; 0 <= i;) {
      do c1 = c0;
      while ((0 <= --i) && ((c0 = chr(i)) <= c1));
      if (0 <= i) {
        *b = j;
        b = SA + --B[c1];
        j = i;
        ++m;
        do c1 = c0;
        while ((0 <= --i) && ((c0 = chr(i)) >= c1));
      }
    }
    if (1 < m) {
      if (flags & (16 | 32)) {
        if (flags & 16) {
          if ((D = SAIS_MYMALLOC(k * 2, sais_index_type)) == NULL) {
            if (flags & (1 | 4)) free(C);
            if (flags & 2) free(B);
            return -2;
          }
        } else D = B - k * 2;
        ++B[chr(j + 1)];
        for (i = 0, j = 0; i < k; ++i) {
          j += C[i];
          if (B[i] != j) SA[B[i]] += n;
          D[i] = D[i + k] = 0;
        }
        LMSsort2(T, SA, C, B, D, n, k, cs);
        name = LMSpostproc2(SA, n, m);
        if (flags & 16) free(D);
      } else {
        LMSsort1(T, SA, C, B, n, k, cs);
        name = LMSpostproc1(T, SA, n, m, cs);
      }
    } else if (m == 1) {
      *b = j + 1;
      name = 1;
    } else name = 0;
    if (name < m) {
      if (flags & 4) free(C);
      if (flags & 2) free(B);
      newfs = (n + fs) - (m * 2);
      if ((flags & (1 | 4 | 8)) == 0) {
        if ((k + name) <= newfs) newfs -= k;
        else flags |= 8;
      }
      RA = SA + m + newfs;
      for (i = m + (n >> 1) - 1, j = m - 1; m <= i; --i)
        if (SA[i] != 0) RA[j--] = SA[i] - 1;
      if (sais_main(RA, SA, newfs, m, name, sizeof(sais_index_type), 0) != 0) {
        if (flags & 1) free(C);
        return -2;
      }
      i = n - 1;
      j = m - 1;
      c0 = chr(n - 1);
      do c1 = c0;
      while ((0 <= --i) && ((c0 = chr(i)) >= c1));
      for (; 0 <= i;) {
        do c1 = c0;
        while ((0 <= --i) && ((c0 = chr(i)) <= c1));
        if (0 <= i) {
          RA[j--] = i + 1;
          do c1 = c0;
          while ((0 <= --i) && ((c0 = chr(i)) >= c1));
        }
      }
      for (i = 0; i < m; ++i) SA[i] = RA[SA[i]];
      if (flags & 4)
        if ((C = B = SAIS_MYMALLOC(k, int)) == NULL) return -2;
      if (flags & 2) {
        if ((B = SAIS_MYMALLOC(k, int)) == NULL) {
          if (flags & 1) free(C);
          return -2;
        }
      }
    }
    if (flags & 8) getCounts(T, C, n, k, cs);
    if (1 < m) {
      getBuckets(C, B, k, 1);
      i = m - 1, j = n, p = SA[m - 1], c1 = chr(p);
      do {
        q = B[c0 = c1];
        while (q < j) SA[--j] = 0;
        do {
          SA[--j] = p;
          if (--i < 0) break;
          p = SA[i];
        } while ((c1 = chr(p)) == c0);
      } while (0 <= i);
      while (0 < j) SA[--j] = 0;
    }
    if (isbwt == 0) induceSA(T, SA, C, B, n, k, cs);
    else pidx = computeBWT(T, SA, C, B, n, k, cs);
    if (flags & (1 | 4)) free(C);
    if (flags & 2) free(B);
    return pidx;
  } // sais_main
  __attribute__((__always_inline__))
  inline int sais(int n, const unsigned char *T, int *SA) {
    if ((T == NULL) || (SA == NULL) || (n < 0)) return -1;
    if (n <= 1) {
      if (n == 1) SA[0] = 0;
      return 0;
    }
    return sais_main(T, SA, 0, n, SAIS_UCHAR_SIZE, sizeof(unsigned char), 0);
  } // sais
 template<typename _Integer>
  int sais(int n, const _Integer *T, int k, int *SA) {
    if ((T == NULL) || (SA == NULL) || (n < 0) || (k <= 0)) return -1;
    if (n <= 1) {
      if (n == 1) SA[0] = 0;
      return 0;
    }
    return sais_main(T, SA, 0, n, k, sizeof(_Integer), 0);
  } // sais
#undef SAIS_UCHAR_SIZE
#undef SAIS_MINBUCKETSIZE
#undef sais_index_type
#undef sais_bool_type
#undef SAIS_LMSSORT2_LIMIT
#undef SAIS_MYMALLOC
#undef chr
} // namespace SAIS

using SAIS::sais;

template<typename _Integer>
int compute_lcp(int n, const _Integer *T, const int *sa, int *rk, int *lcp) {
  if ((T == NULL) || (sa == NULL) || (rk == NULL) || (lcp == NULL) || (n < 0)) return -1;
  for (int i = 0; i < n; ++i) rk[sa[i]] = i;
  for (int i = 0, j = 0; i <= n; ++i) {
    if (rk[i]) {
      if (j) --j;
      for (; T[sa[rk[i]] + j] == T[sa[rk[i] - 1] + j]; ++j);
      lcp[rk[i]] = j;
    }
  }
  return 0;
} // compute_lcp

const int N = 1e6;
int sa[N], rk[N], ht[N];

const int B = 20;
int lg[(N - 1) / B + 1 + 1], st[(N - 1) / B + 1][B], pr[N];

void compute_lcp_rmq(int n) {
    const int SZ = (n - 1) / B + 1;
    for (int i = 2; i <= SZ; i++) lg[i] = lg[i / 2] + 1;
    stack<int> stk;
    int val = 0;
    for (int i = 0; i < n; i++) {
        if (i % B == 0) {
            st[i / B][0] = ht[i];
            while (!stk.empty()) stk.pop();
            val = 0;
        } else {
            st[i / B][0] = min(st[i / B][0], ht[i]);
        }
        while (!stk.empty() && ht[stk.top()] >= ht[i]) {
            val ^= 1 << (stk.top() % B);
            stk.pop();
        }
        val |= 1 << (i % B);
        stk.push(i);
        pr[i] = val;
    }
    for (int i = 1; i <= lg[SZ]; i++) {
        for (int j = 0; j + (1 << i) - 1 < SZ; j++) {
            st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }
}

int lcp_full_block(int l, int r) {
    if (l > r) return infi;
    l /= B;
    r /= B;
    int len = r - l + 1;
    return min(st[l][lg[len]], st[r - (1 << lg[len]) + 1][lg[len]]);
}

int lcp_in_block(int l, int r) {
    return ht[__builtin_ctz(pr[r] >> (l % B)) + l];
}

int lcp(const int i, const int j) {
    if (i == j) out(":(");
    int l = rk[i], r = rk[j];
    if (l > r) swap(l, r);
    l++;
    if (l / B == r / B) return lcp_in_block(l, r);
    
    int lb = l + (((B - l) % B) + B) % B;
    int rb = r - (((r - (B - 1)) % B) + B) % B;
    
    int lcp = lcp_full_block(lb, rb);
    
    if (l != lb) lcp = min(lcp, lcp_in_block(l, lb - 1));
    if (r != rb) lcp = min(lcp, lcp_in_block(rb + 1, r));
    return lcp;
}

char s1[N], s2[N], s3[N];

void solve() {
    int n, m, q;
    n = read(), m = read(), q = read();
    //out(1 << B);
    Getstr(s1, n);
    Getstr(s2, m);
    for (int i = 1; i <= n; i++) s3[i] = s1[i - 1];
    for (int i = n + 1; i <= n + m; i++) s3[i] = s2[i - n - 1];
    sais(n + m + 1, (const unsigned char *) &s3, sa);
	compute_lcp(n + m + 1, (const unsigned char *) &s3, sa, rk, ht);
	compute_lcp_rmq(n + m + 1);
	for (int i = 1; i <= q; i++) {
	    int l1, r1, l2, r2;
	    l1 = read(), r1 = read(), l2 = read(), r2 = read();
	    int l = lcp(l1, n + l2);
	    //out(l);
	    if (l >= (r1 - l1 + 1)) {
	        Putchar('=');
	        Putchar('\n');
	    } else {
	        Putchar("<>"[s1[l1 + l - 1] > s2[l2 + l - 1]]);
	        Putchar('\n');
	    }
	}
	Write();
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
	//cin >> t;
    
    while (t--) {
    	solve(); 
	}
}