/******************************************************************************
* src/tools/lcp.h
*
* Algorithm to calculate the LCP array from a string and suffix array in
* linear time.
*
* Based on Kasai, T., Lee, G., Arimura, H., Arikawa, S., & Park, K. (2001).
* Linear-time longest-common-prefix computation in suffix arrays and its
* applications. 2001. CPM'01 (pp. 181-192). Springer
*
******************************************************************************
* Copyright (C) 2012 Timo Bingmann <tb@panthema.net>
*
* This program is free software: you can redistribute it and/or modify it
* Software Foundation, either version 3 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program.  If not, see <http://www.gnu.org/licenses/>.
*****************************************************************************/

namespace lcp {

template <typename alphabet_type, typename offset_type>
void lcparray(const alphabet_type* string, const offset_type* SA, std::vector<offset_type>& lcp, unsigned int N)
{
// calculate ISA
std::vector<offset_type> ISA (N);

for(unsigned int i = 0; i < N; i++)
ISA[SA[i]] = i;

// allocate lcp vector and iterate over ISA
lcp.resize(N);

unsigned int h = 0; // current height

lcp[0] = 0;
for(unsigned int i = 0; i < N; i++)
{
unsigned int k = ISA[i];
if (k > 0) {
unsigned int j = SA[k-1];
while(i + h < N && j + h < N &&
string[i+h] == string[j+h])
h++;
lcp[k] = h;
}
if (h > 0) h--;
}
}

template <typename alphabet_type, typename offset_type>
void lcparray(const std::vector<alphabet_type>& string, const std::vector<offset_type>& SA, std::vector<offset_type>& lcp)
{
assert(string.size() == SA.size());

lcparray(string.data(), SA.data(), lcp, string.size());
}

template <typename StringContainer, typename SAContainer, typename LCPContainer>
void lcparray_naive(const StringContainer& string, const SAContainer& SA, LCPContainer& lcp)
{
assert( string.size() == SA.size() );
lcp.resize(string.size());

lcp[0] = 0;
for (size_t i = 1; i < string.size(); ++i)
{
typename StringContainer::const_iterator
pa = string.begin() + SA[i-1],
pb = string.begin() + SA[i];

size_t h = 0;

while (pa != string.end() && pb != string.end() && *pa == *pb)
++pa, ++pb, ++h;

lcp[i] = h;
}
}

} // namespace lcp