longest non-overlapping repeating substring

netsetos · web-flow · commit e05cafc69d7b · 2020-11-08T19:14:41.000+05:30
Initial File
diff --git a/longest non overlapping repeating substring b/longest non overlapping repeating substring
@@ -0,0 +1,29 @@
+def longestRepeatedSubstring(str):
+    n = len(str)
+    LRS = [[0 for x in range(n + 1)]for y in range(n + 1)]
+
+    res = ""
+    res_length = 0 
+    index = 0
+    for i in range(1, n + 1):
+        for j in range(i + 1, n + 1):
+            if (str[i - 1] == str[j - 1] and LRS[i - 1][j - 1] < (j - i)):
+                LRS[i][j] = LRS[i - 1][j - 1] + 1
+
+                if (LRS[i][j] > res_length):
+                    res_length = LRS[i][j]
+                    index = max(i, index)
+            else:
+                LRS[i][j] = 0
+    if (res_length > 0):
+        for i in range(index - res_length + 1,
+                       index + 1):
+            res = res + str[i - 1]
+
+    return res
+
+
+if __name__ == "__main__":
+    str = "banana"
+    print(longestRepeatedSubstring(str))
+
