string - Longest Common Substring non-DP solution with O(m*n) -

the definition of problem is:

given 2 strings, find longest common substring.

return length of it.

i solving problem , think solved o(m*n) time complexity. don't know why when solution, it's talking optimal solution being dynamic programming - http://www.geeksforgeeks.org/longest-common-substring/

here's solution, can test here: http://www.lintcode.com/en/problem/longest-common-substring/

int longestcommonsubstring(string &a, string &b) {      int ans = 0;     (int i=0; i<a.length(); i++) {         int counter = 0;         int k = i;         (int j=0; j<b.length() && k <a.length(); j++) {              if (a[k]!=b[j]) {                 counter = 0;                 k = i;              } else {                 k++;                 counter++;                 ans = max(ans, counter);              }           }     }      return ans;         } 

my idea simple, start first position of string , see what's longest substring can match string b, start second position of string , see what's longest substring can match....

is there wrong solution? or not o(m*n) complexity?

good news: algorithm o(mn). bad news: doesn't work correctly.

your inner loop wrong: it's intended find longest initial substring of a[i:] in b, works this:

j = 0 while j < len(b)    match of a[i:] against b[j:]. call s.    remember s if it's longest far found.    j += len(s) 

this fails find longest match. example, when = "xxy" , b = "xxxy" , i=0 it'll find "xx" longest match instead of complete match "xxy".

here's runnable version of code (lightly transcribed c) shows faulty result:

#include <string.h> #include <stdio.h>  int lcs(const char* a, const char* b) {     int al = strlen(a);     int bl = strlen(b);     int ans = 0;     (int i=0; i<al; i++) {         int counter = 0;         int k = i;         (int j=0; j<bl && k<al; j++) {             if (a[k]!=b[j]) {                 counter = 0;                 k = i;             } else {                 k++;                 counter++;                 if (counter >= ans) ans = counter;             }           }     }     return ans;         }  int main(int argc, char**argv) {     printf("%d\n", lcs("xxy", "xxxy"));     return 0; } 

running program outputs "2".