CODEWITHSUNDEEP
javaalgorithm
The Roy
The Roy

Reputation: 2208

Given a string and a non-empty substring, compute recursively the largest substring which starts and ends with the substring and return its length

Given a string and a non-empty substring, compute recursively the largest substring which starts and ends with the substring and return its length.

What I did does not return the correct length. But because I have saved all possible substrings, I could determine the length. Time complexity should be linear: O(n).

This is what I have tried:

public class StringPatternMatcher {

  static String[] array = new String[10];
  static int n = 0;

  public static int findSubString ( String s, String pat) {
    if ( s.length() < pat.length() ) {
        return 0;
    }
    else {
        return s.indexOf(pat);
    }
  }

  public static int findMaxSubstring ( String s, String pat) {
    if ( s.length() < pat.length() ) {
        return 0;
    }
    else if ( s.startsWith(pat, 0)){
        int idx = findSubString( s.substring(pat.length()), pat );
        if ( idx == -1 || idx == 0 ) {
            return -1;
        }
        array[n++] = s.substring(pat.length(), pat.length() + idx);
        return findMaxSubstring( s.substring(pat.length()), pat);
    }
    else {
        return 1 + findMaxSubstring( s.substring(1), pat);
    }       
  }

  public static void main(String[] args) {
    String s = "catwomencatwhiskerscat";
    System.out.println("Count is : " + findMaxSubstring( s, "cat"));
    for ( String str : array) {
        if (str != null )
            System.out.println("The string is:" + str + " and it's len is: " + str.length());
    }
  }
}

Upvotes: 0

Views: 360

Answers (1)

grnc
grnc

Reputation: 527

If you want a linear complexity, you cannot use loops. In this case, the algorithm you can follow;

1- Find first occurrence
2- Find last occurrence (by reversing string and pattern, then doing same step 1)
3- Find real index of last occurrence (by subtracting result of step 2 from length of actual string)
4- Check if result is valid (if result(step3) - result(step1) > 0, then its valid)

Upvotes: 2

Related Questions