c - 查找最长公共(public)子串问题的最小空间复杂度是多少？

Question

const char *_longest_common_substr(const char *s1, const char *s2, int n, int m) {
   // assert n >= m
   int max = 0; // keep track of max length found
   int tmp = 0; // value is incremented till letters match
   int begin = 0;
   int try_begin = 0; // possible new begin index
   int end = 0; // rv = s2[begin : end - 1]
   
   for (int i = 0; i < n; i++) {
       tmp = 0;
       try_begin = 0;
       // s1 is scanned circularly
       for (int j = 0; j < m; j++) {
           int index = (j + i) % n; // current s1 index
           if (index < n && s1[index] == s2[j]) {
               if (tmp == 0)
                   try_begin = j;
               tmp++;
           } else {
               tmp = 0;
           }
           if (tmp > max) {
               max = tmp;
               begin = try_begin;
               end = j + 1;
           }
       }
   }
       
   int size = begin >= end ? 0 : end - begin;
   char *rv = malloc((size + 1) * sizeof(*rv));
   int i;
   for (i = 0; i < size; i++)
       rv[i] = s2[begin + i];
   rv[i] = '\0';
   return rv;
}

const char *longest_common_substr(const char *s1, const char *s2, int n, int m) {
   if (n < m)
       return _longest_common_substr(s2, s1, m, n);
   return _longest_common_substr(s1, s2, n, m);
}

此代码是否正确找到最长的公共(public)子字符串？我不明白为什么在很多地方，例如 wikipedia ，他们使用矩阵来解决问题，而在这个看似简单的解决方案中不需要它，时间复杂度仍然是 O(n*m) 而空间复杂度为 O(1) .
一个可能的测试是

int main() {
    const char *str1 = "identification";
    const char *str2 = "administration";
    
    printf("%s\n", longest_common_substr(str1, str2, strlen(str1), strlen(str2)));
    
}

输出是

ation

子字符串以循环方式使用，因此输入

action
tionac

输出将是

tionac

无论如何，我可以在字符串的末尾添加两个不同的无效字符来删除这个属性

Answer 1

你的算法很奇怪。您只计算最长字符串上的循环子字符串。如果字符串长度相等，则仅在第一个上计算圆形子字符串。
例如:

对于 "bxa"和 "ab"你找到解决方案"ab"因为您在 bxa 上计算循环子字符串

但是对于 "bxa"和 "zaby"您不考虑 "bxa" 中的循环子字符串你找不到"ab"作为解决方案

("abx", "bya")和 ("bya", "abx")即使只有参数的位置发生变化，也有不同的解决方案。 (如果两个参数长度相等，则仅在第一个参数上计算循环子字符串)。

您必须:

根本不计算循环子字符串(维基链接中描述的经典算法)或:

计算两个字符串的循环子字符串(这是一种不同的算法，然后是最长的公共(public)子字符串)

因此，您的算法的复杂性无法与 wiki 算法相提并论，因为它是解决不同问题的不同算法。