RightMaximalPlusOne.java.txt

/**
 * Instructs $SubstringIterator$ to visit only substrings $v$ that are either
 * right-maximal, or such that $pref(v)$ is right-maximal, where $v=pref(v) \cdot a,
 * a \in \Sigma$. $intervals[1+alphabetLength+c]$ contains the interval of
 * $pref(v) \cdot c$ for all $c \in \Sigma$.
 */
public abstract class RightMaximalPlusOne extends RightMaximal {

	protected RightMaximalPlusOne(int alphabetLength, int log2alphabetLength, int textLength, int log2textLength) {
		this.alphabetLength=alphabetLength;
		this.log2alphabetLength=log2alphabetLength;
		this.textLength=textLength;
		this.log2textLength=log2textLength;
		nIntervals=1+(alphabetLength<<1);
		intervals = new long[nIntervals][2];
	}

	protected static Substring getInstance(int alphabetLength, int log2alphabetLength, int textLength, int log2textLength) {
		return new RightMaximalPlusOne(alphabetLength,log2alphabetLength,textLength,log2textLength);
	}

	/**
	 * A string $v$ is extended to the left only if it is right-maximal, or if $pref(v)$
	 * is right-maximal.
	 */
	protected boolean shouldBeExtendedLeft() {
		int rightContext = 0;
		for (int c=0; c<alphabetLength; c++) {
			if (intervals[1+c][1]>=intervals[1+c][0]) rightContext++;
		}
		if (rightContext>1) return true;
		rightContext = 0;
		for (int c=0; c<alphabetLength; c++) {
			if (intervals[1+alphabetLength+c][1]>=intervals[1+alphabetLength+c][0]) rightContext++;
		}
		if (rightContext>1) return true;
	}

}