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

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-检查结果是否有效（如果结果（步骤3）-结果（步骤1)>0，则其有效）