A search has been made for lepton-flavor-violating interactions of the type e+p→lX, where l denotes a μ or τ with high transverse momentum, at a center-of-mass energy √s of 300 GeV with an integrated luminosity of 47.7 pb-1 using the ZEUS detector at HERA. No evidence was found for lepton-flavor violation and constraints were derived on leptoquarks (LQs) that could mediate such interactions. For LQ masses below √s, limits are set on λeq1βlq, where λeq1 is the coupling of the LQ to an electron and a first-generation quark q1 and βlq is the branching ration of the LQ to l and a quark. For LQ masses exceeding √s, limits are set on the four-fermion contact-interaction term λeqα λlqβ/M2LQ for leptoquarks that couple to an electron and a quark qα and also to l and a quark qβ. Some of the limits are also applicable to lepton-flavor-violating processes mediated by squarks in R-parity-violating supersymmetric models. In some cases involving heavy quarks and especially for l=τ, the ZEUS limits are the most stringent published to date.