Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$).
We say that $F$ is searchable if for any $u \in F$ and string $x$, we can find efficiently find a string $s \in F$ such that
- $x$ is a substring of $s \cdot u$
- The number of lexicographically earlier strings $s' \in F$ with this property is $\mathcal o(n)$
We say that $F$ is regex-searchable if instead of requiring $x$ to be a substring of $s \cdot u$, we require $s \cdot u$ to satisfy the $x$ when interpreted as a regular expression.
For any $n$, can find a searchable field with strings of length $>n$? What about a regex-searchable field?