java - 给定一个字符串和一个非空子串，递归计算以该子串开头和结尾的最大子串并返回其长度

Question

给定一个字符串和一个非空子串，递归计算以该子串开头和结尾的最大子串并返回其长度。

我所做的没有返回正确的长度。但是因为我已经保存了所有可能的子字符串，所以我可以确定长度。时间复杂度应该是线性的:O(n)。

这是我试过的:

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());
    }
  }
}

Answer 1

如果你想要线性复杂度，你不能使用循环。在这种情况下，您可以遵循的算法；

1- 查找第一次出现
2- 查找最后一次出现(通过反转字符串和模式，然后执行相同的步骤 1)
3- 找到最后一次出现的真实索引(通过从实际字符串的长度中减去步骤 2 的结果)
4- 检查结果是否有效(如果 result(step3) - result(step1) > 0，则其有效)