LAUSR

We investigate the problem of detecting periodic trends within a string S of length n , arriving in the streaming model, containing at most k wildcard characters, where k = o ( n ). A wildcard character is a special character that can be assigned any other character. We say that S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the prefix of length n − p equals the suffix of length n − p . We present a two-pass streaming algorithm that computes wildcard-periods of S using O ( k 3 polylog n ) $\mathcal {O}(k^{3} \text {polylog} n)$ bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We also give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S with p < n 2 $p<\frac {n}{2}$ and no wildcard characters appearing in the last p symbols of S , using O ( k 3 log 9 n ) $\mathcal {O}(k^{3}\log ^{9} n)$ space.