+ulong TCImplementation::kmismatches(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k) const
+{
+ if (sp>ep) return 0;
+ if (j == 0)
+ {
+ result.push_back(std::make_pair(sp,ep));
+ return ep-sp+1;
+ }
+ int c;
+ ulong spnew;
+ ulong epnew;
+ int knew;
+ ulong sum=0;
+ if (k==0)
+ {
+ sum = searchPrefix(pattern, j, &sp, &ep);
+ if (sp<=ep)
+ result.push_back(std::make_pair(sp, ep));
+ return sum;
+ }
+ vector<int> chars = alphabetrank->accessAll(sp, ep);
+ for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
+ {
+ if (*it == 0)
+ continue; // skip '\0'
+ c = *it;
+ spnew = C[c]+alphabetrank->rank(c,sp-1);
+ epnew = C[c]+alphabetrank->rank(c,ep)-1;
+ if (c!=pattern[j-1]) knew = (int)k-1; else knew = k;
+ if (knew>=0) sum += kmismatches(result, pattern, spnew, epnew, j-1, knew);
+ }
+ return sum;
+}
+
+//first call kerrors(pattern,1,n,m+k,k,d,m), where d[i]=i
+ulong TCImplementation::kerrors(suffix_range_vector &result, uchar const *pattern, ulong sp, ulong ep, ulong j, unsigned k, ulong const *d, ulong m) const
+{
+ if (d[m]<=k) // range of suffixes with at most k-errors found
+ {
+ if (sp<=ep)
+ result.push_back(std::make_pair(sp, ep));
+ return (sp<=ep)?ep-sp+1:0ul;
+ }
+ if (sp>ep || j==0)
+ return 0;
+ ulong *dnew = new ulong[m+1];
+ int c;
+ ulong spnew;
+ ulong p,lowerbound;
+ ulong epnew;
+ ulong sum=0;
+ vector<int> chars = alphabetrank->accessAll(sp, ep);
+ for (vector<int>::iterator it = chars.begin(); it != chars.end(); ++it)
+ {
+ if (*it == 0)
+ continue; // skip '\0'
+ c = *it;
+ spnew = C[c]+alphabetrank->rank(c,sp-1);
+ epnew = C[c]+alphabetrank->rank(c,ep)-1;
+ if (spnew>epnew) continue;
+ dnew[0]=m+k-j+1;
+ lowerbound=k+1;
+ for (p=1; p<=m; p++) {
+ dnew[p]=myminofthree(d[p]+1,dnew[p-1]+1,(c==pattern[m-p])?d[p-1]:(d[p-1]+1));
+ if (dnew[p]<lowerbound)
+ lowerbound = dnew[p];
+ }
+ if (lowerbound<=k)
+ sum += kerrors(result, pattern, spnew, epnew, j-1, k,dnew,m);
+ }
+ delete [] dnew;
+ return sum;
+}
+