## 3 Algorithm I: Basic Algorithm
### Conflict Resolution  
We use the notions of **conflict sequence** or **conflict pairs**. Two suffixes \(T^{\prime}_{i}\) and \(T^{\prime}_{j}\) form a conflict sequence in \(T\) if \(T^{\prime}_{i}[0\ldots k]=T^{\prime}_{j}[0\ldots k]\), (that is, \(T[i\ldots i+k]=T[j\ldots j+k]\) ) for some \(k\geq 1\). Thus, the two suffixes can not be assigned a total order after considering their first \(k\) symbols. We say that the conflict between \(T^{\prime}_{i}\) and \(T^{\prime}_{j}\) is resolved whenever \(T[i\ldots i+l_{k}-1]=T[j\ldots j+l_{k}-1]\), and \(T[i+l_{k}]\
eq T[j+l_{k}]\). Here, \(l_{k}\) is called the conflict length. We call the triple \((T^{\prime}_{i},T^{\prime}_{j},l_{k})\) a conflict pair, or conflict sequence. We use the notation \(CP(i,j,l_{k})\) to denote a conflict pair \(T^{\prime}_{i}\) and \(T^{\prime}_{j}\) with a conflict length of \(l_{k}\). We also use \(CP(i,j)\) to denote a conflict pair where the conflict length is yet to be determined, or is not important given the context of the discussion. The challenge, therefore, is how to resolve conflicts efficiently given the recursive partitioning framework proposed. Obviously, \(l_{k}\leq n\), the sequence length. Thus, the minimum distance from the start of each conflicting suffix to the end of the sequence (\(\min\{n-i,n-j\}\)), or the distance from an already sorted symbol can determine how long it will take to resolve a conflict. Here, we consider how the previously resolved conflicts can be exploited for a quick resolution of other conflicts. We maintain a traceback record on such previously resolved conflicts in a **conflict tree**, or a **conflict table**. Figure 2 shows the conflict tree for the example sequence, T=aaaabaaabxaaab. Without loss in generality and for easier exposition of the basic methodology, we assume that \(n=2^{x}\), for some positive integer \(x\). Our conflict resolution strategy is based on the following properties of conflict sequences and conflict trees. 1. Given the even-odd recursive partitioning scheme, at any given recursion level, conflicts can only occur between specific sets of positions in the original sequence \(T\). For instance, at the lowest level, conflicts can only occur between \(T_{0}\), and \(T_{n/2}\), or more generally, between \(T_{i}\), and \(T_{i+n/2}\). See Figure 2.  
2. Given the conflict sequence, \(T^{\prime}_{i}\) and \(T^{\prime}_{j}\) the corresponding conflict pair \(CP(i,j,l_{k})\) is unique in \(T\). That is, only one conflict pair can have the pair of start positions \((i,j)\). Thus the conflict pairs \(CP(i,j,l_{k})\) and \(CP(j,i,l_{k})\) are equivalent. Hence, we represent both \(CP(i,j,l_{k})\) and \(CP(j,i,l_{k})\) as \(CP(i,j,l_{k})\), where, \(i<j\). 3. Consider \(CP(i,j)\) at level \(h,0\leq h\leq\lceil\log n\rceil\) in the tree. We define its **neighbors** as the conflict pairs: \(CP(i^{\prime},j^{\prime})\), with \((i^{\prime}=i+2^{q},j^{\prime}=j+2^{q})\), or \((i^{\prime}=i-2^{q},j^{\prime}=j-2^{q})\), where \(q>0\), with \(q=h,h-1,h-2,\ldots,1\), and \(i^{\prime},j^{\prime}\leq n\). Essentially, neighboring conflicts are found on the same level in the conflict tree, from the leftmost node to the current node. For example, for \(R_{6}=CP(2,14)\) at \(h=2\), the neighbor will be: \(\{R_{2}=CP(0,12)\}\). We notice that, by our definition, not all conflicts in the same node are neighbors. **Figure 2.** Conflict tree for the example sequence \(T=aaaabaaaaab\). The original sequence is indicated at the root node. The notation \(R_{i}\mapsto R_{j}\) indicates that conflict pair \(R_{i}\) is resolved by \(R_{j}\) after a certain number of steps, given that \(R_{j}\) has been resolved. Conflict pairs are labeled following a depth-first traversal on the tree. Given the conflict tree, we can determine whether a given conflict pair \(CP(i,j)\) can be resolved based on previous trace back information (_i.e._, previously resolved conflicts). From the conflict tree, we see that this determination can be made by checking only a **fixed** number of neighboring conflict pairs.