Two strings str1 and str2, find longest common substring

Two strings str1 and str2, find longest common substring
A new method:
Build the hash table based on all substring from str1. O(n^2)
For each substring from str2, lookup the hash table and keep the max length of substring. O(n^2)

How to find longest repeated substring

How to find longest repeated substring
Find longest common substring between str and str, arr[i][j]=arr[i-1][j-1]+1,if(str[i]==str1[j])
arr[i][j]=0 if(str[i]!=str1[j])
note, we should the ignore diagonal of the arr which is the str itself
The complexity is O(N^2)
Or use suffix tree which is O(n), not easy to code

Longest common substring

Longest common substring

int f(int* a, int* b, int n)
{
int arr[n][n];
int max=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==0)//first row
{
if(a[i]==b[j]) {arr[i][j]=1; if(max<arr[i][j]) max=arr[i][j];}
else arr[i][j]=0;
}
else if(j==0)//first col
{
if(a[i]==b[j]) {arr[i][j]=1; if(max<arr[i][j]) max=arr[i][j];}
else arr[i][j]=0;
}
else 
{
if(a[i]==b[j]) {arr[i][j]=arr[i-1][j-1]+1; if(max<arr[i][j]) max=arr[i][j];}
else arr[i][j]=0;
}
}
return max;
}

Write a function to find the longest palindrome from a string.

Write a function to find the longest palindrome from a string.

Suppose the string is str, you reverse the str get strr, make a suffix tree for these two strings. If palindrome is like “cabbad”, for every i find LCA of suffix i of str and suffix m-i+1of strr
If palindrome is like “dacab”, for every i find LCA of suffix i of str and suffix m-i of strr
Find maximal LCA, this O(n)
or
Use dynamic programming, find longest common substring with str and strr, O(n^2)
This is not right
forward T: ABCXYYZCBA
reverse T: ABCZYYXCBA
The longest common substring is ABC, but the longest palindromic substring is just YY.