Algorithm to find the most common substrings in a string

by

This is as task similar to Nussinov algorithm and actually even simpler as we do not allow any gaps, insertions or mismatches in the alignment.

For the string A having the length N, define a F[-1 .. N, -1 .. N] table and fill in using the following rules:

  for i = 0 to N
    for j = 0 to N
      if i != j
        {
          if A[i] == A[j]
            F[i,j] = F [i-1,j-1] + 1;
          else
            F[i,j] = 0;
        }

For instance, for B A O B A B:

AlgChart

This runs in O(n^2) time. The largest values in the table now point to the end positions of the longest self-matching subquences (i – the end of one occurence, j – another). In the beginning, the array is assumed to be zero-initialized. I have added condition to exclude the diagonal that is the longest but probably not interesting self-match.

Thinking more, this table is symmetric over diagonal so it is enough to compute only half of it. Also, the array is zero initialized so assigning zero is redundant. That remains

  for i = 0 to N
    for j = i + 1 to N
      if A[i] == A[j]
         F[i,j] = F [i-1,j-1] + 1;

Shorter but potentially more difficult to understand. The computed table contains all matches, short and long. You can add further filtering as you need.

On the next step, you need to recover strings, following from the non zero cells up and left by diagonal. During this step is also trivial to use some hashmap to count the number of self-similarity matches for the same string. With normal string and normal minimal length only small number of table cells will be processed through this map.

I think that using hashmap directly actually requires O(n^3) as the key strings at the end of access must be compared somehow for equality. This comparison is probably O(n).

More Related Contents:

  1. Finding all possible combinations of numbers to reach a given sum
  2. What is tail call optimization?
  3. How to convert floats to human-readable fractions?
  4. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  5. How do I check if a number is a palindrome?
  6. Is there an O(n) integer sorting algorithm?
  7. Why is quicksort better than mergesort?
  8. Data structures for loaded dice?
  9. Pseudorandom Number Generator – Exponential Distribution
  10. Determine font color based on background color
  11. Algorithm to generate anagrams
  12. Natural Sorting algorithm
  13. What is the fastest integer factorization algorithm?
  14. design a stack such that getMinimum( ) should be O(1)
  15. Is there an algorithm for color mixing that works like mixing real colors?
  16. How to read values from numbers written as words?
  17. Find the missing and duplicate elements in an array in linear time and constant space
  18. Find the first un-repeated character in a string
  19. Function for creating color wheels [closed]
  20. Efficiently reverse the order of the words (not characters) in an array of characters
  21. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  22. What is a bubble sort good for? [closed]
  23. Iterating over a Binary Tree with O(1) Auxiliary Space
  24. How do I find a factorial? [closed]
  25. Best way of calculating n choose k?
  26. Peak detection of measured signal
  27. Algorithm for permutations of operators and operands
  28. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  29. Tournament bracket placement algorithm
  30. How to convert decimal fractions to hexadecimal fractions?

Leave a Comment